最长不含重复字符的子字符串

这个题目要求我们找到一个字符串中不包含重复字符的最长连续子串的长度。换句话说，我们需要在给定的字符串中，找出一段连续的字符序列，这个序列里的所有字符都是唯一的，并且我们希望这段序列尽可能地长。

1. 问题理解与举例
假设我们有一个字符串 "abcabcbb"。我们需要找到最长的不含重复字符的子字符串。

• 我们从第一个字符 'a' 开始看，"a" 本身没有重复。
• "ab" 也没有重复。
• "abc" 也没有重复。
• 当我们试图加入下一个 'a' 时，发现 'a' 在 "abc" 中已经出现过了，所以以第一个字符 'a' 开头的最长无重复子串是 "abc"，长度为3。
• 但整个字符串的最长子串不一定是从第一个字符开始的。例如，从第二个字符 'b' 开始的无重复子串 "bca" 长度也是3。
• 实际上，整个字符串 "abcabcbb" 的最长无重复字符子串是 "abc" (或者后面的 "bca", "cab")，长度是3。

另一个例子："bbbbb"，最长无重复子串就是任何一个字符本身，长度为1。
再一个例子："pwwkew"，最长无重复子串是 "wke" (或 "kew")，长度为3。注意 "pwke" 不是连续子串，因为原字符串中是 'p', 'w', 'w', 'k', 'e', 'w'，字符 'w' 重复了。

2. 核心思路与暴力法
最直接的想法是暴力枚举所有可能的子串，然后检查它们是否有重复字符。

• 枚举所有起始索引 i (从0到n-1) 和结束索引 j (从i到n-1)。
• 对于每个子串 s[i:j]，检查其中是否有重复字符。我们可以用一个集合来记录子串中的字符，逐个添加，如果某个字符已经在集合中，则说明有重复。
• 记录所有无重复子串的最大长度。
  这个方法的时间复杂度是 O(n³)，因为枚举子串是 O(n²)，检查重复又需要 O(n)。对于长字符串效率极低。

3. 优化思路：滑动窗口
我们可以使用“滑动窗口”技术来优化。窗口就是字符串中由左右指针 left 和 right 界定的一段连续子串。我们保证窗口内的字符始终是无重复的。

• 我们使用两个指针（索引）left 和 right，初始都指向字符串开头（索引0）。
• 我们用一个哈希集合 charSet 来实时记录当前窗口内包含的字符。
• 然后，我们不断将 right 指针向右移动，尝试扩大窗口。
  • 如果 s[right] 这个字符不在 charSet 中，说明加入它是安全的，窗口依然无重复。我们就把它加入集合，并更新当前窗口长度（right - left + 1），并记录最大长度。
  • 如果 s[right] 已经在 charSet 中，说明出现了重复。这时我们不能简单地把 s[right] 加进来。为了保持窗口无重复，我们需要移动 left 指针来收缩窗口，直到将那个与 s[right] 重复的字符移出窗口为止。
    • 具体做法是：将 left 指针指向的字符从 charSet 中移除，然后 left 右移一位。重复此过程，直到 s[right] 这个字符不在集合中了。
    • 然后，我们才能将 s[right] 加入集合，并继续。
• 这样，right 指针会遍历整个字符串一次，而 left 指针也只会向右移动，不会回溯。所以两个指针各遍历一次，时间复杂度是 O(n)。

让我们用例子 "abcabcbb" 模拟一下：

1. left=0, right=0: charSet={}, 加入 'a' -> {'a'}, 窗口长度=1，最大长度=1。
2. right=1: 'b' 不在集合，加入 -> {'a','b'}, 窗口长度=2，最大长度=2。
3. right=2: 'c' 不在集合，加入 -> {'a','b','c'}, 窗口长度=3，最大长度=3。
4. right=3: 字符是 'a'，但 'a' 已经在集合中。此时需要收缩窗口：从集合移除 s[left] 即 'a'，left右移->1。现在集合是 {'b','c'}，'a' 仍不在集合？不，我们移除了一个'a'，但我们现在检查的字符 'a' 还是不在当前集合 {'b','c'} 中。所以停止收缩。加入 'a' -> {'b','c','a'}，此时left=1, right=3，窗口长度=3。
5. right=4: 'b' 在集合中。收缩：移除 s[left]='b' (left=1), left右移->2，集合变为 {'c','a'}，'b' 不在集合了。加入 'b' -> {'c','a','b'}，窗口长度=3。
6. right=5: 'c' 在集合中。收缩：移除 s[left]='c' (left=2), left右移->3，集合变为 {'a','b'}，'c' 不在了。加入 'c' -> {'a','b','c'}，窗口长度=3。
7. right=6: 'b' 在集合中。收缩：移除 s[left]='a' (left=3), left右移->4，集合变为 {'b','c'}，'b' 还在！继续：移除 s[left]='b' (left=4), left右移->5，集合变为 {'c'}，'b' 不在了。加入 'b' -> {'c','b'}，窗口长度=2。
8. right=7: 'b' 在集合中。收缩：移除 s[left]='c' (left=5), left右移->6，集合变为 {'b'}，'b' 还在！继续：移除 s[left]='b' (left=6), left右移->7，集合变为 {}，'b' 不在了。加入 'b' -> {'b'}，窗口长度=1。
   结束。遍历过程中记录的最大长度是3。

4. 进一步优化：使用哈希映射记录索引
上面的方法在发现重复字符时，left 指针需要一步一步移动，直到移出重复字符。我们可以用哈希映射（字典）来记录每个字符最近一次出现的位置索引，这样我们可以直接跳到正确的位置。

• 我们定义一个字典 charIndexMap，键是字符，值是该字符最近一次出现的索引。
• 我们仍然使用 left 和 right 指针界定窗口。
• 当 right 向右移动，查看字符 c = s[right]：
  • 如果 c 不在字典中，或者虽然出现过，但其上一次出现的索引 < left（说明这个重复字符不在当前窗口内，不影响），那么我们直接可以扩展窗口。
  • 否则，说明 c 在当前窗口内重复出现了。那么我们需要把 left 指针直接移动到该字符上一次出现位置的下一个索引，即 left = charIndexMap[c] + 1。这样才能保证新窗口没有重复。
  • 然后，无论是否移动left，我们都更新字符 c 在字典中的索引为当前的 right。
  • 当前窗口的长度是 right - left + 1，我们用它更新最大长度。

这种方法更直接，left 的移动是跳跃式的，效率更高。

用 "abcabcbb" 再模拟一下：

1. left=0, right=0, char='a'：不在字典中，记录 {'a':0}，长度=1，最大长度=1。
2. right=1, char='b'：不在，记录 {'a':0, 'b':1}，长度=2，最大长度=2。
3. right=2, char='c'：不在，记录 {'a':0, 'b':1, 'c':2}，长度=3，最大长度=3。
4. right=3, char='a'：在字典中，且上次索引0 >= left(0)，重复！移动 left = 0+1 = 1。更新 'a' 的索引为3。此时窗口为 s[1:3]即"bca"，长度=3。
5. right=4, char='b'：在字典中，上次索引1 >= left(1)，重复！移动 left = 1+1 = 2。更新 'b' 索引为4。窗口为 s[2:4]即"cab"，长度=3。
6. right=5, char='c'：在字典中，上次索引2 >= left(2)，重复！移动 left = 2+1 = 3。更新 'c' 索引为5。窗口为 s[3:5]即"abc"，长度=3。
7. right=6, char='b'：在字典中，上次索引4 >= left(3)，重复！移动 left = 4+1 = 5。更新 'b' 索引为6。窗口为 s[5:6]即"cb"？等一下，left变成了5，right是6，所以窗口是 s[5:6]="b"？不对，因为 left 跳到了5，但 s[5] 是 'c'（索引5是字符'c'），s[6]是 'b'，所以窗口是 "cb"，长度=2。
8. right=7, char='b'：在字典中，上次索引6 >= left(5)，重复！移动 left = 6+1 = 7。更新 'b' 索引为7。窗口为 s[7:7]="b"，长度=1。
   结束。最大长度始终为3。

5. 算法步骤总结

1. 初始化 left = 0，maxLength = 0，创建一个空字典 charIndexMap。
2. 遍历字符串，索引 right 从 0 到 n-1：
   a. 当前字符 ch = s[right]。
   b. 如果 ch 在 charIndexMap 中，并且其存储的索引 >= left（说明在当前窗口内），则更新 left = charIndexMap[ch] + 1。
   c. 无论是否更新了 left，都更新 charIndexMap[ch] = right。
   d. 计算当前窗口长度 currentLength = right - left + 1，如果大于 maxLength，则更新 maxLength。
3. 遍历结束后，maxLength 即为答案。

6. 代码示例（Python）

def lengthOfLongestSubstring(s: str) -> int:
    char_index = {}  # 哈希映射，存储字符最近出现的索引
    left = 0
    max_len = 0

    for right in range(len(s)):
        ch = s[right]
        # 如果字符出现过且在当前窗口内（索引>=left）
        if ch in char_index and char_index[ch] >= left:
            left = char_index[ch] + 1  # 收缩左边界
        # 更新字符的索引
        char_index[ch] = right
        # 计算当前窗口长度
        current_len = right - left + 1
        if current_len > max_len:
            max_len = current_len

    return max_len

7. 复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串长度。我们只遍历了一次字符串，每个字符的查找和插入操作在哈希表中是平均 O(1) 的。
• 空间复杂度：O(min(m, n))，其中 m 是字符集的大小（例如ASCII是128）。在最坏情况下，我们可能需要存储整个字符串中所有不重复的字符。