[LeetCode] 3. Longest Substring Without Repeating Characters (Medium)

반복되는 문자가 없는 가장 긴 substring을 구하는 문제입니다.

hash를 사용하여, 앞에서부터 차례대로 true 처리를 해주었습니다. hash에서 이미 true가 된 문자가 나올 경우, maxLen을 갱신해주었고 앞 글자를 제외하여 다시 for문을 돌도록 하였습니다. 이 때, 앞 글자에서부터 차례대로 확인하지 않고, 이전 for문에서 확인된 부분까지는 건너뛰고 그 다음부터 확인하도록 하였습니다.

 

class Solution {
public:
    unordered_map<char,bool> map;
    
    int lengthOfLongestSubstring(string s) {
        int maxLen = 0;       
        int len = 1;
        
        for(int i=0;i<s.size(); i++)
        {   
            map[s[i]] = true;
            for(int j=i+len; j<s.size();j++)
            {
                if(map[s[j]] == true)
                {
                    maxLen = (len > maxLen) ? len:maxLen;
                    if(s[i] != s[j])
                    {
                        map[s[i]] = false;
                        len--;
                    }
                    break;
                }
                else
                {
                    map[s[j]] = true;
                    len++;
                }
            }
            maxLen = (len > maxLen) ? len:maxLen;
        }
        
        return maxLen;
    }
};