Longest Substring Without Repeating Characters

快慢指针经典题，这类题思想就是通过快慢指针拉出一个不定范围的sliding window，在这些不定长的sliding window中找到符合要求的解，具体到此题，因为要找的是非重复最长子字符串，所以必须使用哈希表做滑动窗口的载体，首先想到的是用set来对字符串的重复进行检查，下面是代码

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        n = len(s)
        slow = 0
        fast = 0
        checker = set([])
        res = 0
        count = 0

        while slow < n:
            while fast < n and s[fast] not in checker:
                checker.add(s[fast])
                count += 1
                fast += 1
            res = max(count, res)
            checker.remove(s[slow])
            slow += 1
            count -= 1
            if fast >= n:
                break

        return res

上面的count是用来记录临时非重复字符子串的长度的，这里注意的是，因为慢指针是一格一格往前走的，所以count也是一次减一

然而实际上这道题还可以继续优化，因为当快指针移动到一个重复字符时，我们可以直接让慢指针跳到这个重复字符在当前子字符串中的位置的前面一格，因此可以使用dict来记录字符串的相应位置，LeetCode上面的这种解法很不直观，不觉得是好办法

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        Map<Character, Integer> map = new HashMap<>(); // current index of character
        // try to extend the range [i, j]
        for (int j = 0, i = 0; j < n; j++) {
            if (map.containsKey(s.charAt(j))) {
                i = Math.max(map.get(s.charAt(j)), i);
            }
            ans = Math.max(ans, j - i + 1);
            map.put(s.charAt(j), j + 1);
        }
        return ans;
    }
}