[Leetcode] 3. Longest Substring Without Repeating Characters

---

Given a string s, find the length of the longest substring without repeating characters.

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Constraints:

• 0 <= s.length <= 5 * 104
• s consists of English letters, digits, symbols and spaces.

반복되지 않는 가장 긴 substring

일단 substring이라는 건 "abcd"에 대해 ["a", "ab", "abc", "abcd", "b", "bc", "bcd", "c", "cd", "d"] 이렇게 나올 수 있는 것

근데 반복되지 않는... 이 말을 이해하기 어려웠는데 substring에 같은 문자가 2개없는 이라고 생각하면 될 것 같다.

abc는 가능하지만 abca는 안되는 것(a가 2개 있으니까)

Solution 1. unordered_set 

sliding window 방식으로 글자를 앞에서 부터 한글자씩 set에 넣으면서 글자가 이미 set에 있으면 해당 글자를 뺐을때 최대한 긴 set가 됐을 때를 고르면 되는데, 이때 unordered_set 을 쓰면 된다.

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> charSet;
        int n = s.length();
        int max = 0;
        int left = 0;
        
        for (int right =0;right<n;right++){
            if (charSet.count(s[right])){
                while(charSet.count(s[right])){
                    charSet.erase(s[left]);
                    left++;
                }
                charSet.insert(s[right]);
            }
            else{
                charSet.insert(s[right]);
                if (max<(right-left+1)){
                    max = right-left+1;
                }
            }
        }
        return max;
    }
};

Solution 2. unordered_map 

unordered_set대신 undordered_map을 쓰게 되면 <문자, index> 식으로 저장해서 set의 경우 left문자열이 나왔을 경우 left 문자열을 찾을때 까지 지웠다면 그 부분만 index를 사용해서 점프하는 방식으로 사용 가능

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.length();
        int maxLength = 0;
        unordered_map<char, int> charMap;
        int left = 0;
        
        for (int right = 0; right < n; right++) {
            if (charMap.count(s[right]) == 0 || charMap[s[right]] < left) {
                charMap[s[right]] = right;
                maxLength = max(maxLength, right - left + 1);
            } else {
                left = charMap[s[right]] + 1;
                charMap[s[right]] = right;
            }
        }
        
        return maxLength;
    }
};

Solution 3. Integer Array

charIndex 라는 것을 두고 어떤 문자에 대해 index값을 저장하고 left가 새로 들어온 right문자의 index 보다 커야 반복되지 않았다는 것을 의미. (근데 왜 128이지 그냥 크게 둔 값인가, s는 영문자, 숫자, 특수문자가 가능하다고 했는데 그 경우의 수가 128을 넘지않으려나?-> Yes, Since there are 128 ASCII characters maximum size of array required is 128.이라고 답변 달려있었음 )

예를들어 a가 이미 index 2에 값이 있었는데 4에 또 나왔다면, left는 3이 되어야 a를 뺄 수 있는 꼴

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.length();
        int maxLength = 0;
        vector<int> charIndex(128, -1);
        int left = 0;
        
        for (int right = 0; right < n; right++) {
            if (charIndex[s[right]] >= left) {
                left = charIndex[s[right]] + 1;
            }
            charIndex[s[right]] = right;
            maxLength = max(maxLength, right - left + 1);
        }
        
        return maxLength;
    }
};

 

1, 2, 3순서로 submit해봤는데 뒤로 갈 수록 성능이 좋아짐