LeetCode 3 Longest Substring Without Repeating Characters

发表于 | 分类于 | 阅读次数：

LeetCode第三题，找最长的没有重复字符的子串。

题目大意

给一个字符串，求它里面最长的没有重复字符的子串的长度。

举个例子：

1
2
3
"abcabcbb"
"bbbbbb"
"pwwkew"

上面三个字符串的结果应该是3, 1, 3。

解决方案

先来一个简单的

暴力一点的方案，从某一个位置开始，找这个位置开始的没有重复字符的子串的长度，然后取最大值。

（感觉想一个比较暴力的方法有时候还更难一些）

比如对第一个例子abcabcbb，从第0位开始，到第四位时重复了，长度为3。然后再从第1位b开始。

我们可以知道当没有一个字符重复的时候，算法需要跑$O(N^3)$的时间。

改进

在上面的暴力算法当中，我们的判断方式有非常多的重复工作，比如先找到了abc，又找到了bca，这样的过程重叠太多了。此外判断有没有重复的时候每次都需要遍历当前的字符串，可能也是一个浪费。

我们尝试分别对这两个缺陷进行改进。

首先我们可以确定一件事情，如果我们截掉了一个字符串的一部分，那么这个部分肯定不会比被截的这个长。我们可以把继续判断的位置从重复出现的位置开始。

然后判断是否有重复的时候还得遍历字符串，这个我们可以用一些空间来解决这个问题，记录当前子串的开始位置和每一个字符最后出现的位置就可以了。我们可以使用哈希表来干这种事情，查起来就比遍历快多了。

那么我们得到了一个更快的办法，这个办法似乎被称为滑动窗口法。

思路就是记录当前子串的起始位置和终止位置。它们组成的窗口里面就是当前判断的子串，我们不停地将终止位置向字符串右端移动，通过哈希表判断下一个字符的位置是否大于起始位置，并进行相应的滑动操作，在这个过程中窗口大小的最大值就是我们要的结果。

哈希表里面取元素的时间是$O(1)$，我们从前往后遍历一遍字符串的时间是$O(N)$。也就是我们只需要$O(N)$的时间就可以得出结果。

算法描述

不知道怎么样描述算法比较像LaTeX的风格…试试代码框好了。

1
2
3
4
5
6
7
8
9
10
Input: str
Init begin, end, max 0;
hm := HashMap<Char, Int>;
while end <= str.len:
    end ++;
    if str[end] in hm and hm[str[end]] > begin:
        begin := hm[str[end]] + 1;
    hm[str[end]] = end;
    update max;
return max;