[LeetCode 3] Longest Substring Without Repeating Characters

作者 Shilei Tian 日期 2017-05-01
[LeetCode 3] Longest Substring Without Repeating Characters

题目要求

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

解题思路

乍一看,这道题目似乎与字符串很有关系,因为涉及到了子串的长度问题。但是实际上,仔细观察,你就会发现,字符串只是承载题目信息的一个载体,而抽象出问题的本质来看,题目的要求就变成,在一个序列中找一个区间,使得该区间内不含重复元素。仔细想一下,是不是这个要求?

这样看来,题目的要求就很清晰了。最无脑的办法,就是枚举区间的所有可能的位置,然后再检查该区间内元素是否有重复的,时间复杂度为 $O(n^2)$。那么有没有高效地算法呢?比如,只扫一遍数组的?答案是:有的。

本题有个关键点,就是区间是连续的,也就是题目要求中的 substring,而不是 subsequence,那么我们就可以用类似滑动窗口的办法,来进行扫描。先假设这个子串的开始位置为 0,向右扫描,记录每一个元素的出现情况。当扫描到一个元素已经出现过时,假设它之前出现的位置为 i,当前的位置为 j,我们就可以断定:任意开始位置小于 i,结束为止为 j 的子串,都包含重复元素。所以,为了检查 j 后面是否有更长的子串,我们必须将字符串的开始位置设置为 i + 1。每次进行扫描的时候,顺带求一下子串的长度,亦即区间的长度,其实就等于当前位置 j 与开始位置 start 的差再加上 1。因此,为了高效运算,我们将 start 的初始位置设置为 -1

最终的代码如下:

class Solution {
public:
int lengthOfLongestSubstring(string s) {
vector<int> dict(256, -1);
int maxLen = 0, start = -1;
for (int i = 0; i != s.size(); ++i) {
if (dict[s[i]] > start)
start = dict[s[i]];
dict[s[i]] = i;
maxLen = max(maxLen, i - start);
}
return maxLen;
}
};