LeetCode 无重复字符的最长子串

给定一个字符串 s，找出其中不含有重复字符的最长子串的长度。

• 示例 1:

  输入: s = "abcabcbb"

  输出: 3

  解释: 无重复字符的最长子串是 "abc"，长度为 3。

• 示例 2:

  输入: s = "bbbbb"

  输出: 1

  解释: 无重复字符的最长子串是 "b"，长度为 1。

• 示例 3:

  输入: s = "pwwkew"

  输出: 3

  解释: 无重复字符的最长子串是 "wke"，长度为 3。注意 "pwke" 是子序列，不是子串。

要解决这个问题，我们需要找到字符串中最长的无重复字符的子串。可以使用滑动窗口（Sliding Window）的方法来高效地解决这个问题。滑动窗口是一种常用的处理字符串或数组子区间问题的技术，通过维护一个窗口（通常由两个指针表示）来动态调整子区间的范围。

1. 使用两个指针 start 和 end 分别表示窗口的起始和结束位置。
2. 初始化时，start 和 end 都指向字符串的开始（即 0）。
3. 移动 end 指针扩展窗口，直到窗口内出现重复字符。
4. 当出现重复字符时，移动 start 指针到重复字符的下一个位置，以排除重复字符。
5. 在移动指针的过程中，记录窗口的最大长度。

• 如何快速判断窗口内是否有重复字符？可以使用哈希表（字典）来记录字符最近出现的位置。
• 当遇到重复字符时，start 指针应该移动到 max(start, 重复字符的下一个位置)，以确保窗口内没有重复字符。

提供的代码中有两种实现方法，主要区别在于如何处理重复字符时 start 指针的更新。

• 特点：

  当遇到重复字符时，start 更新为 max(start, ditt[s[end]])。

  ditt[s[end]] 存储的是 end + 1，即重复字符的下一个位置。

• 问题：

  这种更新方式可能会导致 start 指针回退。例如，对于字符串 "abba"，当 end 指向第二个 'a' 时，start 会被更新为 ditt['a'] = 1，但实际上 start 已经移动到 2（因为 'b' 重复），因此 start 不应该回退。

  因此，这种方法在某些情况下可能无法正确计算最长子串。

• 特点：

  当遇到重复字符时，start 更新为 max(start, ditt[s[end]] + 1)。

  ditt[s[end]] 存储的是 end，即重复字符的当前位置。

• 优点：

  这种方法确保 start 指针不会回退，因为 ditt[s[end]] + 1 是重复字符的下一个位置，而 start 已经可能更大（例如之前因为其他字符重复而移动过）。

  因此，这种方法是正确的。

方法二是正确的实现。以下是其详细解释：

1. 初始化 start 和 end 为 0，ditt 为空字典，res 为 0。
2. 遍历字符串：

   如果 s[end] 在 ditt 中，说明字符重复，更新 start 为 max(start, ditt[s[end]] + 1)。

   更新 res 为当前窗口长度 end - start + 1 和 res 的较大值。

   将 s[end] 的位置更新为 end（即 ditt[s[end]] = end）。

   移动 end 指针。

3. 返回 res。

以 s = "abba" 为例：

• 初始：start = 0, end = 0, ditt = {}, res = 0。
• end = 0 ('a'):

  'a' 不在 ditt 中。

  res = max(0, 0 - 0 + 1) = 1。

  ditt = {'a': 0}。

  end = 1。

• end = 1 ('b'):

  'b' 不在 ditt 中。

  res = max(1, 1 - 0 + 1) = 2。

  ditt = {'a': 0, 'b': 1}。

  end = 2。

• end = 2 ('b'):

  'b' 在 ditt 中，ditt['b'] = 1。

  start = max(0, 1 + 1) = 2。

  res = max(2, 2 - 2 + 1) = 2。

  ditt = {'a': 0, 'b': 2}。

  end = 3。

• end = 3 ('a'):

  'a' 在 ditt 中，ditt['a'] = 0。

  start = max(2, 0 + 1) = 2。

  res = max(2, 3 - 2 + 1) = 2。

  ditt = {'a': 3, 'b': 2}。

  end = 4。

• 结束，返回 res = 2。

以下是正确的实现代码：

• 时间复杂度：O(n)，其中 n 是字符串的长度。end 指针最多移动 n 次，start 指针最多移动 n 次。
• 空间复杂度：O(min(m, n))，其中 m 是字符集的大小。最坏情况下需要存储所有字符。