LeetCode: 3. Longest Substring Without Repeating Characters

처음에는 Brute Force로 할까? 했지만... 문제를 읽어보니

전형적인 투포인터 문제라는 것을 알 수 있었다.

 

[메인 로직]

만약 처음나온 문자가 나온다면, num++을 해주고 map에 해당 문자를 추가해주었고 End++해주었다.

하지만 이미 나왔던 문자가 나온다면 num--해주고 map에서 해당 문자를 제거한 후 Start++해주었다.

 

Two Pointer 방식

시간복잡도 : O(n)

// 투포인터
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int ans = 0;
        int Start=0, End = 0;
        map<char, int> m;
        int num = 0;
        while(Start<=End && End<s.size()){
            if(m.count(s[End])==0){
                num++;
                m[s[End]] = 1;
                End++;
            }else{
                num--;
                m.erase(s[Start]);
                Start++;
            }
            ans = max(ans, num);
        }
        return ans;
    }
};