[LC3] Longest Substring Without Repeating Characters

Monday, January 7, 2019

这道算法题来自 LeetCode #3:找出最长不含重复字符的连续子串长度。这里使用了滑动窗口并结合不同的数据结构 —— SetMap ——提供了两种实现版本。

滑动窗口

sliding window [i, j]

设定一个 $[i, j]$ 的滑动窗口。

$j$ 不断向前扫描未访问过的字符;对于 $i$,当且仅当 $j$ 遇到已访问过的字符时,才向前移动。

在 $i$ 扫描过程中,滑动窗口的长度 j - i + 1 为当前不含重复字符的子串长度。这一系列长度值中的最大者即为所求结果。

接下来,我们使用两种方式来记录 $j$ 访问过的字符。

Solution#1 使用 Set 记录访问过的字符

为了记录滑动窗口内 $j$ 已访问的字符,我们可以用到 Set 数据结构。这里为了便于实现,直接用了 JavaScript Object 来充当 Set。

type VisitedMap = {
  <char: string>: boolean
}

这样,每次 $j$ 扫描到一个字符 char 时,将其放入 Set,然后继续向前移动,直到遇到一个访问过的字符。此时, $i$ 把自己所指向的字符从 Set 中移除,然后向前移动,接着 $j$ 开始扫描下一个字符。重复整个过程,直到 $j$ 扫描到最后一个字符。

const map = {}
...
while (i < sarray.length && j < sarray.length) {
    if (!map[sarray[j]]) {
        map[sarray[j]] = true
        max = Math.max(max, j - i + 1)
        j++
    } else {
        map[sarray[i]] = false
        i++
    }
}

复杂度分析

对于长度为 n 的字符串:

  • 时间复杂度:最坏情况下,即该字符串只有一个字符且重复 n 次,每个字符会被 $i$ 和 $j$ 分别访问两次,所以时间复杂度是 $O(2n) = O(n)$
  • 空间复杂度:最坏情况下,即该字符串的每个字符都不相同时,空间复杂度为 $O(n)$,否则空间复杂度为去重字符串后的长度 $O(m)$

Solution#2 使用 Map 记录访问过的字符下标

optimized sliding window [i, j]

LeetCode 提供的 Solutions - Approach 3: Sliding Window Optimized 找到了更好的解决方法。它使用了 Map 结构来记录访问过的字符索引:

Instead of using a set to tell if a character exists or not, we could define a mapping of the characters to its index. Then we can skip the characters immediately when we found a repeated character. The reason is that if $s[j]$ have a duplicate in the range $[i, j)$ with index $j′$, we don’t need to increase $i$ little by little. We can skip all the elements in the range $[i, j′]$ and let $i$ to be $j′ + 1$ directly.

type VisitedMap = {
  <char: string>: number
}

Solution#1 的实现用了 JavaScript Object 来存储访问过的字符,其中 Key 为访问过的字符,Value 为当前滑动窗口对应字符是否被访问的结果。现在我们把 Value 换成已访问字符的下一个索引。

每当 $j$ 访问了一个字符,则把字符放入 Map 并把值置为 $j + 1$。当 $j$ 重复访问到字符时,$i$ 就能快速跳到下一个窗口位置,即 i = Math.max(i, map[sarray[j]])

const map = {}
...
for (let i = 0, j = 0; j < sarray.length; j++) {
  if (contains(map, sarray[j]) {
    i = Math.max(i, map[sarray[j])
  }
  max = Math.max(max, j - i + 1)
  map[sarray[j]] = j + 1
}

复杂度分析

对于长度为 n 的字符串:

  • 时间复杂度:只需要 $j$ 访问 $n$ 个字符,所以时间复杂度为 $O(n)$
  • 空间复杂度:最坏情况下,即该字符串的每个字符都不相同时,空间复杂度为 $O(n)$,否则空间复杂度为去重字符串后的长度 $O(m)$