runtime 4 ms, beats 96.46% of cpp submissions
O(n) solution with explanation

tags: string, pointer, sliding window

Longest Substring Without Repeating Characters

📖 description

給定一個字串 s ，找到一個不包含重複字元的最長子字串
ex. pwwkew -> wke 為不包含重複字元的最長子字串

🧠 solution

sliding window，維護一個紀錄所有字母出現次數的 map ，以及兩個指標表示當前子字串的範圍，並根據兩種 case 做出操作

  • 目前沒有出現重複的字元，右指標向右走以獲得更長的子字串
  • 目前出現了重複的字元，左指標向右走直到沒有出現重複的字元

⏳ time complexity

最糟狀況下走過兩次字串
總時間複雜度 O(n)

📝 code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.size()==0){
            return 0;
        }
        vector<int> cnt(128,0);
        int n=0;
        int left=0,right=0;
        int ma = 0;
        while(right<=s.size()){
            if(n==0){
                ma = max(ma,right-left-1); // 當前最佳解
                if(cnt[s[right]]==0){      // 如果下一個字元沒有出現過
                    cnt[s[right++]]++;     
                }
                else{                      // 出現重複的字元 
                    cnt[s[right++]]++; 
                    n++;
                }
            }
            else{
                if(cnt[s[left]]>=2){       // 沒有重複的字元
                    cnt[s[left++]]--;
                    n--;
                }
                else{
                    cnt[s[left++]]--;     // 還有字元重複
                }
            }   
        }
        return ma+1;
    }
};