[LeetCode - 3] Longest Substring Without Repeating Characters - C++

분류: 큐 /

 

문제

문제 링크

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.

 

풀이

- STL 큐 이용

int lengthOfLongestSubstring(string s) {
    bool used[256] = {};
    queue<int> q;
    int ans = 0;
    for(char c:s){
        if(used[c]) {
            while(!q.empty() && q.front() != c){
                used[q.front()] = false;
                q.pop();
            }
            if(!q.empty()) 
                q.pop();
            q.push(c);
        } else {
            used[c] = true;
            q.push(c);
        }

        if(ans < q.size()) 
            ans = q.size();
    }
    return ans;
}

- 투포인터를 큐처럼 활용

int lengthOfLongestSubstring(string s) {
    bool used[256] = {};
    int ans = 0;
    for(int left=0, right=0, n=s.length(); right<n; ans=max(ans,++right-left)){
        int x = s[right];
        if(used[x]){
            while(left < right && s[left] != x){
                used[s[left++]] = false;
            }
            if(left < right) left++;
        } else used[x] = true;
    }
    return ans;
}

처음에 알파벳만 있는줄알고 26개로 used 배열을 잡았으나 이런 저런 문자 다 있는걸 확인하고 캐릭터 문자 `char` 사이즈인 1바이트 256으로 잡아줬다.