3. 无重复字符的最长字串
- 题目:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 >给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
>示例 1:
>输入: "abcabcbb"
>输出: 3
>解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
>示例 2:
>输入: "bbbbb"
>输出: 1
>解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
>示例 3:
>输入: "pwwkew"
>输出: 3
>解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
>来源:力扣(LeetCode)
>链接:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
>著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路:
首先理论上的最低时间复杂度应该为
$$
\Omega(N)=N
$$
,因为至少要遍历一遍字符串。开始把题目理解错了,题目的意思应该是选中的子字符串中无重复字符。那么最暴力的做法就是两层循环,时间复杂度
O(N^2)
;问题可以转化为:我们用什么策略选择字符串,再用什么策略判断是否有重复字符?或者再转换一下思路,最长无重复字符的字符串一定是这个子字符串的后一个字符存在于子字符串中,或者为空,那么我们就去找两端为相同字符的左闭合区间,而无区间嵌套的最长区间长度为答案(特别地,只有一个的字符为空区间,不存在任何嵌套,但长度为1);
以上思路实现:遍历字符串,存储所有key的indices,构建无序符号表(不需要按key大小排序),并判断其他重复字符串的所有区间是否与当前区间嵌套(内嵌套)。(注:实现太过复杂,嵌套循环太多)
题解为滑动窗口:其核心思想其实就是从头开始遍历字符串,统计当前最长的无重复子字符串,出现重复时抛弃旧值增加新值,并更新窗口大小,直至遍历结束。其利用的特性为子字符串必须是连续的,而输出仅要求长度,因此只记录最大长度就好。
滑动窗口实现:由于要维持一个窗口,并且期间还要查重,如果重复还有改变窗口大小,因此用队列实现窗口,用哈希表实现查重。
我的代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24class Solution {
public:
int lengthOfLongestSubstring(string s) {
if(s.empty()) return 0;
queue<char> q;
unordered_set<char> m;
int len = 0;
int max = 1;
for(const auto& c:s){
q.push(c);
auto res = m.insert(c);
if(res.second == false){
while(q.front() != *res.first){
m.erase(q.front());
q.pop();
}
q.pop();
}
len = q.size();
max = max>len?max:len;
}
return max;
}
};需要注意的点是,如果新入队的元素有重复,那么中间所有出队的元素要从set中删除。
优化:实际上要表示窗口,我们不需要用队列的额外内存,用两个指针(迭代器)表示边界即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26class Solution {
public:
int lengthOfLongestSubstring(string s) {
if(s.empty()) return 0;
unordered_set<int> lookup;
auto left = s.cbegin();
auto right = s.cbegin();
int len = 1;
int maximum = 1;
lookup.insert(*left);
while(right != s.cend()){
++right;
auto res = lookup.insert(*right);
if(res.second == false){
while(*left != *right){
lookup.erase(*left);
++left;
}
++left;
}cout<<*left<<endl;
len = right==s.cend()?right-left:right-left+1;
maximum = max(len, maximum);
}
return maximum;
}
};时间复杂度:
O(N)
,每个字符访问一次,空间复杂度:O(1)
,空间消耗为哈希表内存占用,为常数空间。