题目链接:https://leetcode.com/problems/longest-substring-without-repeating-characters/

题目描述:给定字符串 s , 找到不重复子串的最大长度。

题目限制:

  • 字符串长度 $[0, 10^4]$
  • 字符串中包括字母、数字、符号和空格

思路一:Brute-Force

  1. 枚举子串 s[i...j] 的起点 i 和终点 j ;$O(n^2)$
  2. 判断当前子串 s[i...j] 是否存在重复字符(每次构造 Set);$O(n)$
  3. 如果不存在重复字符,计算长度并且维护出现的最大长度。$O(1)$

这个方法过于暴力,在当前数据规模 $O(n^3)$ 的实现必然超时,就不实现了。

思路二:Hash Table + Sliding Window

对于子区间问题,经常会根据其局部一致的特性使用双指针或滑动窗口技巧。

上面的方法中需要对每个可能子串都检查其中是否有重复元素,这造成了大量开销。不难发现,如果一个子串 s[i...j] 中不存在重复字符,那么对于子串 s[i...j+1], 只需要查找 s[j+1] 是否在 s[i...j] 中出现过即可,区间 [i...j] 可被看作是滑动的窗口,我们需要根据上述情况,在每次滑动的同时对窗口区间进行扩展或者收缩,使其满足题目的约束条件:

  • 如果 s[j+1]s[i...j] 中已经出现过,则需要调整窗口起点 i 和终点 j 的位置;
  • 如果 s[j+1]s[i...j] 中未曾出现过,则只需要调整窗口终点 j 的位置;

通过使用滑动窗口,避免了对 ij 的枚举,将这一步的时间复杂度从 $O(n^2)$ 降低到了 $O(n)$. 接下来考虑如何查找 s[j+1]s[i...j] 中是否出现过,通过在窗口滑动的过程中维护一个哈希表,可以将查询的时间从 $O(n)$ 降低到 $O(1)$. 这个哈希表的 Key 是字符,Value 其是上一次出现的位置索引,这样的设置同时方便对 i 进行更新。

当然不同的更新策略将导致不同的代码具体实现,下面这种比较简洁优雅:

时间复杂度:$O(n)$ – 窗口线性滑过整个字符串

空间复杂度:$O(\min (m, n))$ – 其中 $m$ 指字符集个数

接下来考虑细节上的优化,由于给定了字符范围,可以使用 vector 代替 unordered_map 实现简单的哈希表,这样做虽然在某些情况下增加了空间开销(字符串 s 长度非常小时),但降低了 STL 哈希表构造的时间开销。另外通过初始化默认索引值为 -1, 可以去掉上面对 if 语句的判断(初始化成 0 不行),从而再减少一行代码量:

时间复杂度:$O(n)$ – 窗口线性滑过整个字符串

空间复杂度:$O(m)$ – 其中 $m$ 指字符集个数

思路三:DP & Optimize

对于最大/最长系列问题,如果一下子想不到最直观的解法,可以尝试一下动态规划。

使用 $dp[i]$ 表示以 $s[i]$ 为结尾的最长无重复字符的子串长度,最终取 $\max (dp[0] … dp[l-1])$, 其中 $l$ 为字符串 $s$ 长度。

以 $s[i-1]$ 为结尾的最长无重复字符的子串为 $s[i-dp[i-1] … i-1]$, 转移方程为:

$$dp[i]=\begin{cases} dp[i-1] + 1 & \text{如果 $s[i]$ 不在 $s[i-dp[i-1] … i-1]$ 中}\\ i-k & \text{如果 $s[i]=s[k]$, 其中 $k \in s[i-dp[i-1] … i-1]$} \end{cases} $$

代码如下:

时间复杂度:$O(n^2)$

空间复杂度:$O(n)$

不难发现,上面的思路中也存在着对 $s[i]$ 是否在 $s[i-dp[i-1] … i-1]$ 区间中的判断,所以可以和思路二一样,遍历过程中维护一个哈希表结构来减少查找的时间:

时间复杂度:$O(n)$

空间复杂度:$O(n+m)$ – 其中 $m$ 指字符集个数