3. 无重复字符的最长子串

https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

使用语言：golang

func lengthOfLongestSubstring(s string) int {
    charSets := make(map[string]int)
    result := 0
    start := 0
    for i, char := range s {
        pos, ok := charSets[string(char)]
        if ok && start <= pos {
            start = pos + 1
        }
        
        charSets[string(char)] = i
        if i - start + 1 > result {
            result = i - start + 1
        }
    }
    
    return result
}

我先构造了一个 map 结构用来记录字符出现的位置，用 start 记录子串的起始位置，用 result 记录最长子串的长度。

然后遍历整个字符串，当发现某个字符已经在之前出现过时，判断该字符上次出现的位置是否是在子串的起始位置之后，即子串中是否已经出现过该字符。在这种字符发生重复的情况下，我们的当前子串的长度已经无法增长下去了，要开始统计一个新的子串长度了，新的子串从哪里开始呢？从重复字符所在位置的下一个位置开始，因为之前的位置已经没有意义的，他们的长度一定小于当前子串的长度。因此 start = pos + 1。

当前字符的位置 - 子串的起始位置 + 1 就是子串的长度。

我们这样遍历了一遍字符串，就得到了最大的子串长度。

总结

这个问题的子问题是字符 s[i] 在 [start, i) 中是否有字符与其重复，发生重复的位置就是 pos。而 [start, pos] 是 [start, i - 1] 的一个子串，所以可以直接将其忽略，从 pos + 1 的位置开始继续寻找最长子串。

痕迹
没有过去，就没法认定现在的自己