[Leetcode] Longuset Substring Without... 풀어보기

https://leetcode.com/problems/longest-substring-without-repeating-characters/description/?utm_source=chatgpt.com

Longest Substring Without Repeating Characters - LeetCode

 

Subsequence가 아니라 Substring을 찾는 문제입니다.

 

기본적으로는 sliding window방식으로 진행했습니다.

다만 이런문제는 여러 경우에서 디테일이 필요하기에 실수하기가 쉬워보입니다.

 

물론 제가 실수해서 하는 말이구요 LeetCode는 틀린 케이스에 대해 제공해주기 때문에 이를 통해서 디버깅하면서 수정했습니다.

 

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int len = s.size();

        for (int i = 0; i < len; ++i)
        {
            char curch = s[i];
            auto it = charMap.find(curch);
            if (it != charMap.end())
            {
                if (laststartidx > it->second)
                {
                    curlen = i - laststartidx + 1;
                }
                else
                {
                    curlen = i - it->second;
                    laststartidx = it->second + 1;
                }
                charMap[curch] = i;
            }
            else
            {
                charMap[curch] = i;
                ++curlen;
            }
        maxlen = max(maxlen, curlen);
        }
        return maxlen;
    }

    unordered_map<char, int> charMap;
    int maxlen = 0;
    int curlen = 0;
    int laststartidx = 0;
};

 

핵심적인 부분은 현재 중복이 발생해 갱신이 필요할 때 무엇을 기준으로 갱신할지입니다.

문자 c가 마지막으로 등장한 index, 현재 중복 없는 substring의 시작 index 

 

이 2가지를 비교하는 것이 핵심적입니다.

---

AI에게 물어본 결과 세부적인 수정사항은 있으나 시간복잡도가 바뀌는 정도의 문제는 없다고합니다.