无重复字符的最长子串

问题拆解

给定字符串 s，要找出其中不含重复字符的最长子串的长度。注意是子串（连续）而不是子序列。

暴力做法是枚举所有子串再逐个检查是否有重复字符，时间复杂度 O(n³)，即使用集合优化检查也还是 O(n²)。真正值得抓住的性质是：如果 [left, right] 里出现了重复，那么所有以这些字符开头、更长的子串也一定重复——没必要一个个重新验证。

让 [left, right] 始终表示一个没有重复字符的子串。右边界负责探索新字符，出现冲突时，左边界负责恢复窗口的合法性。

滑动窗口

用一个字典 last_seen 记录每个字符最近一次出现的下标。右边界每纳入一个字符，如果它在当前窗口内出现过，就把左边界直接跳到旧位置的下一格：

public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> lastSeen = new HashMap<>();
    int left = 0, answer = 0;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        if (lastSeen.containsKey(c) && lastSeen.get(c) >= left) {
            left = lastSeen.get(c) + 1;
        }
        lastSeen.put(c, right);
        answer = Math.max(answer, right - left + 1);
    }
    return answer;
}

def lengthOfLongestSubstring(s: str) -> int:
    last_seen = {}
    left = 0
    answer = 0

    for right, char in enumerate(s):
        if char in last_seen and last_seen[char] >= left:
            left = last_seen[char] + 1

        last_seen[char] = right
        answer = max(answer, right - left + 1)

    return answer

func lengthOfLongestSubstring(s string) int {
    lastSeen := make(map[byte]int)
    left, answer := 0, 0
    for right := 0; right < len(s); right++ {
        c := s[right]
        if pos, ok := lastSeen[c]; ok && pos >= left {
            left = pos + 1
        }
        lastSeen[c] = right
        if right-left+1 > answer {
            answer = right - left + 1
        }
    }
    return answer
}

pub fn length_of_longest_substring(s: String) -> i32 {
    let mut last_seen = std::collections::HashMap::new();
    let (mut left, mut answer) = (0usize, 0usize);
    for (right, ch) in s.bytes().enumerate() {
        if let Some(&pos) = last_seen.get(&ch) {
            if pos >= left {
                left = pos + 1;
            }
        }
        last_seen.insert(ch, right);
        answer = answer.max(right - left + 1);
    }
    answer as i32
}

最容易错的地方：更新左边界时必须判断旧位置是否还在当前窗口中（last_seen[char] >= left）。否则，遇到 abba 时，最后一个 a 的旧下标 0 已经在窗口外，若不加判断会让左边界错误地向后退。

左右边界都只向前走、不回头，所以两个指针各自最多移动 n 次，整体是线性的。

复杂度

指标	复杂度	原因
时间	`O(n)`	左右边界各自最多前进 n 次
空间	`O(k)`	k 为字符集大小，字典最多存这么多键

可以迁移的模式

答案来自连续区间，且区间的合法性容易判断；
右边界扩张破坏合法性时，左边界右移能够恢复；
两个边界都不会向后退，因此总移动次数是线性的。

看到“最长/最短的满足某条件的子串（子数组）”，先想想能不能让一个窗口边走边保持合法。