[leetcode] 3. Longest Substring Without Repeating Characters

처음 이 문제를 보았을 땐 set만 이용해서 풀 수 있을거라 생각했다.
set에 넣은 값이 있으면 count를 증가시킨 후 maxCount를 최종적으로 리턴하면 해당 3개의 케이스는 풀 수 있었다.

#include <set>
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        set<char> sets;
        int count = 0;
        int maxCount = 1;

        if(s.size() == 0){
            return 0;
        }
        for(int i = 0 ; i < s.size();i++){
            if(sets.find(s[i]) != sets.end()){
                maxCount = max(count, maxCount);
                count = 1;
                continue;
            }
                sets.insert(s[i]);
                count++;
        }
        maxCount = max(count, maxCount);
        return maxCount;
    }
};

문제는 dvdf 와 같은 경우가 문제가 되었다.

결국 풀이를 보고 풀었는데 우선 Sliding Window 기법을 통해 풀어야 했다.
물론 완탐을 통해 풀 수 도 있다고는 한다.

여하튼 보자면 right가 하나씩 움직이면서 set에 포함된 값을 찾게 되면
left를 한 칸씩 움직이면서 해당 set에 저장된 문자열을 하나씩 지운다.
이후 더 이상 right에 중복이 일어나지 않는다면, right는 계속 앞으로 가다가
만약 또 한 번 중복이 일어나면 현재까지 left와 멀어진 길이를 비교해 maxCount에 넣어주고
반복하는 개념이다.

#include <set>
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        set<char> sets;
        int maxCount = 0;
        int left = 0;
        for(int right = 0 ; right < s.size();right++){
            if(sets.find(s[right]) == sets.end()){
                maxCount = max(maxCount,right+1-left);
                sets.insert(s[right]);
            }else{
                while(sets.find(s[right]) != sets.end()){
                    sets.erase(s[left]);
                    left++;
                }
                sets.insert(s[right]);
            }
        }
        return maxCount;
    }
};