3. 無重複的最長子串

推薦事前閱讀：滑動窗口

思路

這個題目跟209. 長度最小的子數組不同，上次要找最短，這次找最長，但想法是類似的。
不斷的往右邊延伸，除非萬不得已，否則不要移動左邊的指針。
另外，在移動左指針時，可以紀錄之前字元出現過的位置，
左指針至少要移動到上次出現的位置之後，才能讓窗口內的字元沒有重複，是一種優化方式。

程式碼

1. 滑動窗口

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.length();
        unordered_map<char, int> freq;
        int res = 0;
        for(int i = 0, j = 0; j < n; j++) {
            freq[s[j]]++; // 不斷的延伸右邊
            while(freq[s[j]] > 1) { // 加入的字符出現次數太多了, 縮減左邊，直到滿足條件
                freq[s[i++]]--;
            }
            // 這時窗口中的子字串是滿足條件的，列入參考
            res = max(res, j - i + 1);
        }
        return res;
    }
};

2. 滑動窗口 優化

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.length();
        unordered_map<char, int> lastPos; // 紀錄字元上次出現的位置
        int res = 0;
        for(int i = 0, j = 0; j < n; j++) {
            if(lastPos.contains(s[j])) { // 如果已經出現過, 左邊界必須要位於上次出現位置的右邊
                i = max(i, lastPos[s[j]] + 1); // 盡量往右, 避免回跳
            }
            res = max(res, j - i + 1);
            lastPos[s[j]] = j;
        }
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(1)$