题目描述
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
样例1
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
样例2
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
样例3
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
算法1
(双指针+哈希表) $O(n)$
比较暴力的思想是枚举所有子串,然后判断子串是否合法,这样时间复杂度是 $O(n^3)$ 的。我们考虑怎么优化,可以发现这道题具有单调性:对于每个终点其实都存在最远的一个起点使得窗口内子串合法,那么当终点右移的时候,起点也一定会右移,不然它就不是上一个终点最远的起点了。
所以我们可以用双指针扫描,并且用一个哈希表记录窗口内的字符,当右端点移动时如果窗口不合法那就只可能是右端点的字符多余了,我们不断地移动左端点直到窗口合法。
C++ 代码
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> mp;
int res = 0;
for (int i = 0, j = 0; i < s.size(); i ++ )
{
mp[s[i]] ++ ;
while (mp[s[i]] > 1)
{
mp[s[j]] -- ;
j ++ ;
}
res = max(res, i - j + 1);
}
return res;
}
};
算法2
(优化版双指针) $O(n)$
在上一个算法中,当右端点字符多余时,我们需要不断地移动左端点使得窗口合法。其实我们可以直接一步把左端点移动到正确的位置,那就是窗口内右端点字符最后一次出现的位置
后面。
所以我们可以用哈希表记录所有字符最后一次出现的位置,不过由于它会记录从起点到当前右端点内的所有字符而不只是窗口内的字符,所以我们还需要判断一下字符出现的位置是不是还在窗口内,即mp[s[i]] >= j
。
C++ 代码
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> mp;
int res = 0;
for (int i = 0, j = 0; i < s.size(); i ++ )
{
if (mp.count(s[i]) && mp[s[i]] >= j) j = mp[s[i]] + 1;
mp[s[i]] = i;
res = max(res, i - j + 1);
}
return res;
}
};