无重复字符的最长子串

题目

给定一个字符串 s ,请你找出其中不含有重复字符的最长子串 的长度。

  1. 示例 1:输入: s = “abcabcbb” 输出: 3
  2. 示例 2:输入: s = “bbbbb” 输出: 1
  3. 示例 3:输入: s = “pwwkew” 输出: 3
  4. 示例 4:输入: s = “” 输出: 0

分析该题的滑动窗口模型

初始时两个指针都指向字符串的开头。此时子串中只有一个字符,满足子串中字符不重复这条件,但是还不是最优的

我们使用滑动窗口的思想来计算最优解: 若右指针的下一个字符与该子串中的字符不重复,则右指针右移,增大窗口边界;若重复了,则左指针右移重新检测子串,直到右指针移动到字符串末尾。用两指针之差来计算字符串长度。

然后这道题的关键就是如何检测右指针的下一个字符是否与子串中的字符重复

第一个想法 是再遍历一次子串,判断是否重复。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
bool judge(string &s,int l,int r){
for(int i=l;i<r;i++)
for(int j=r;j>i;j--)
if(s[i]==s[j]) return false;
return true;
}
int lengthOfLongestSubstring(string s) {
if(s.size()==1) return 1;
int len=0,l=0,r=0;
while(r+1<s.size()){
if(judge(s,l,r+1)) r++;
else l++;
if(r-l+1>len) len=r-l+1;
}
return len;
}
};
judge1

典型以时间换空间了。不行!

第二个想法是 构造一个无序的集合来储存已经出现的字符。利用`unordered_set`的`count()`函数来检测一个字符是否在子串中出现。出现返回1,否则为0。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if(s.size()==0) return 0;
if(s.size()==1) return 1;
unordered_set<char> usc;
int l=0,r=0,ans=0;
usc.insert(s[r]);
while(r+1<s.size()){
if(!usc.count(s[r+1])){
r++;
usc.insert(s[r]);
}
else{
ans=max(ans,r-l+1);
usc.erase(s[l]);
l++;
}
}
ans=max(ans,r-l+1);
return ans;
}
};
judge2

看来性能还是一般般,还有更好的方法!这个方法的缺陷就是从无序集合中查找元素还会消耗一些时间。那么我们能不能无需查找就直到该元素的位置?这时应该想到数组的查地址查找,时间复杂度$O(n)$。

第三个想法是 构造一个下标0~127的整型数组,用来储存数组下标所对应的字符的出现次数。若一个字符对应下标为0,则在子串中没有出现,反之出现。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
int lengthOfLongestSubstring(string& s) {
int len=s.size(),l=0,r=0,ans=0;
if(len==0) return 0;
if(len==1) return 1;
vector<int> vc(128,0);
vc[s[r]]=1;
while(r+1<len){
if(!vc[s[r+1]]){
r++;
vc[s[r]]=1;
}
else{
vc[s[l]]=0;
ans=max(ans,r-l+1);
l++;
}
}
ans=max(ans,r-l+1);
return ans;
}
};
judge3

有一说一,这个算法牛逼。然而我写的代码并不是很优美,所以看起来很长。但是换个角度来说可读性还是不错的,希望以后还能看懂🙏。

字符串的排列

题目

给你两个字符串 s1 和 s2 ,写一个函数来判断 s2 是否包含 s1 的排列。如果是,返回 true ;否则,返回 false 。换句话说,s1 的排列之一是 s2 的 子串 。

  1. 示例 1:输入:s1 = “ab” s2 = “eidbaooo” 输出:true
  2. 示例 2:输入:s1 = “ab” s2 = “eidboaoo” 输出:false

提示:s1 和 s2 仅包含小写字母

分析该题的滑动窗口模型

我们在s2上维护一个和s1相同大小的窗口。

要判断s1的排列之一是否是s2的子串,只需要不断地比较s1和s2窗口对应的子串即可。如果s1的一个排列和该子串相同,则返回true;否则该窗口向右移动,重新判断,直到窗口到达s2边界。

于是,解决这道题的关键就是如何判断s2的子串是s1的一个排列。

现在我们吸收上一题的经验,使用一个数组来记录字符串中字母出现的次数。

想法: 先记录s1中字母出现的次数,然后不断判断地用另一个数组记录s2窗口中字符出现的次数。如果两个数组相等,那么s1 的排列之一就是 s2 的 子串,返回true;否则窗口右移。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
bool checkInclusion(string& s1, string& s2){
vector<int> vi(26,0);
for(auto j:s1) vi[j-97]++;
int len=s1.size(),i=0;
while(i+len<=s2.size()){
vector<int> v(26,0);
for(int j=i;j<i+len;j++) v[s2[j]-97]++;
if(v==vi) return true;
i++;
}
return false;
}
};

很可惜,这个想法的思路是没有问题的,但是时间复杂度为$O(mn)$,性能很低!

judge1

我们来分析一下上面做法的问题:窗口每次向右移动时,只会向右移动一格的距离,但是我们却重新遍历了一遍窗口中的字符,耗掉了很多时间。实际上我们只需要更新端点即可:原窗口最左边的字符出现次数-1,新窗口最右边字符出现的次数+1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
bool checkInclusion(string& s1, string& s2){
int len1=s1.size(),len2=s2.size();
if(len1>len2) return false;
vector<int> vi(26,0),vj(26,0),i=0;
for(;i<len1;i++){
vi[s1[i]-97]++;
vj[s2[i]-97]++;
}
if(vj==vi) return true;;
for(;i<len2;i++){
vj[s2[i]-97]++;
vj[s2[i-len1]-97]--;
if(vj==vi) return true;
}
return false;
}
};
judge2

这下性能就很不错了啊~

总结
  1. 掌握滑动窗口的基本思想:左右移动窗口或缩放窗口,寻找可行解或最优解。
  2. 滑动窗口可以看成模型。在此基础上,我们还要思考如何寻找比较好的算法来优化判断条件。这个需要我们多练习来熟悉常用的方法。