3. Longest Substring Without Repeating Characters

O(n) 用hashmap维护下标
l表示上一个发生重复的位置

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        d = {}
        res, l = 0, -1
        for r, c in enumerate(s):
            l = max(l, d.get(c, -1))
            res = max(res, r - l)
            d[c] = r
        return res

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> f(256, -1);
        int n = s.length();
        int res = 0;
        for (int r = 0, l = -1; r < n; ++r) {
            l = max(l, f[s[r]]); // 更新l
            f[s[r]] = r; // 更新表
            res = max(res, r - l); // 更新res
        }
        return res;
    }
};

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> hm(256, -1);
        int n = s.length();
        int start = -1;
        int res = 0;
        for (int i = 0; i < n; ++i) {
            start = max(start, hm[s[i]]); // 一定要用max更新start，否则见反例abba
            hm[s[i]] = i;
            res = max(res, i - start);
        }
        return res;
    }
};

O(n) two pointers

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        bool hashmap[256] = {false};
        int n = s.length();
        int res = 0;
        for (int i = 0, j = i; i < n; ++i) {
            while (j < n && !hashmap[s[j]]) {
                hashmap[s[j++]] = true;
            }
            res = max(res, j - i);
            hashmap[s[i]] = false;
        }
        return res;
    }
};