滑动窗口核心算法解决字符串问题(最小覆盖子串/字符串排列/异位词/最长无重复子串)
滑动窗口核心算法解决字符串问题
滑动窗口概览
滑动窗口技巧主要解决子数组问题，比如寻找符合某个条件最长/最短的子数组。
思想：维护一个窗口，不断滑动，更新答案
int left = 0, right = 0;
while (right < nums.size()) {
// 增大窗口
window.addLast(nums[right]);
right++;
while (window needs shrink) {
// 缩小窗口
window.removeFirst(nums[left]);
left++;
}
}
-
基于滑动窗口算法框架写出的代码，时间复杂度是 O(N)，比嵌套 for 循环的暴力解法效率高。
-
指针
left, right不会回退（它们的值只增不减），所以字符串/数组中的每个元素都只会进入窗口一次，然后被移出窗口一次，不会说有某些元素多次进入和离开窗口，所以算法的时间复杂度就和字符串/数组的长度成正比。
伪代码框架：
void slidingwindow(string s){
//合适数据结构记录窗口数据 map/int
auto window= ;
int left=0,right=0;
//窗口扩大(必做)
while(right<s.size()){
//c是将移入窗口的字符
char c=s[right];
window.add(c);
//增大窗口
right++;
//进行一系列操作
...
//判断左侧是否要收缩(选做)
while(window needs shrink){
//d是一处窗口的字符
char d=s[left];
window.remove(d);
//缩小窗口
left++;
//进行窗口内数据一系列操作
...
}
}
}
这两个 ... 处的操作分别是扩大和缩小窗口的更新操作，其实它们操作是完全对称的。
LeeCode案例
一、最小覆盖子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
思路：
- 双指针–>左右指针—>
[left, right)---->一个「窗口」(方便窗口内只有一个元素) - 增大窗口，直到
[left, right)包含t - 停止增大，开始缩小窗口，直到不符合要求，不 包含
t - 重复2,3
第 2 步相当于在寻找一个「可行解」，然后第 3、4 步在优化这个「可行解」，最终找到最优解
图解：
增大窗口，直到包含t：
缩小窗口：
不再符合条件：
之后重复上述过程，先移动 right，再移动 left…… 直到 right 指针到达字符串 S 的末端，算法结束。
完整代码：
class Solution {
public:
string minWindow(string s, string t) {
unordered_map<char, int> need, window;
for (char c : t) {
need[c]++;
}
int left = 0, right = 0;
// 记录window中的字符满足need条件的字符个数
int valid = 0;
// 记录最小覆盖子串的起始索引及长度
int start = 0, len = INT_MAX;
while (right < s.size()) {
// c 是将移入窗口的字符
char c = s[right];
// 扩大窗口
right++;
// 进行窗口内数据的一系列更新
if (need.count(c)) {
window[c]++;
if (window[c] == need[c])
valid++;
}
// 判断左侧窗口是否要收缩
while (valid == need.size()) {
// 在这里更新最小覆盖子串
if (right - left < len) {
start = left;
len = right - left;
}
// d 是将移出窗口的字符
char d = s[left];
// 缩小窗口
left++;
// 进行窗口内数据的一系列更新
if (need.count(d)) {
if (window[d] == need[d])
valid--;
window[d]--;
}
}
}
// 返回最小覆盖子串
return len == INT_MAX ? "" : s.substr(start, len);
}
};
二、字符串排列
给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。
换句话说，s1 的排列之一是 s2 的 子串 。
注意哦，输入的 s1 是可以包含重复字符的，所以这个题难度不小。
思路：
不再赘述，主要是看更新窗口需要有什么变化
主要思考以下问题：
- 什么时候扩大窗口，窗口加入字符时，应该更新那些数据？
- 窗口什么时候停止扩大，此时又该更新哪些数据？
- 我们要的结果应该在扩大还是缩小窗口时更新？
完整代码：(cp后改)-------错
class Solution {
public:
// 判断 s 中是否存在 t 的排列
bool checkInclusion(string t, string s) {
unordered_map<char, int> need, window;
for (char c : t) {
need[c]++;
}
int left = 0, right = 0;
// 记录window中的字符满足need条件的字符个数
int valid = 0;
// 不需记录最小覆盖子串的起始索引及长度
//int start = 0, len = INT_MAX;
while (right < s.size()) {
// c 是将移入窗口的字符
char c = s[right];
// 扩大窗口
right++;
// 进行窗口内数据的一系列更新
if (need.count(c)) {
window[c]++;
if (window[c] == need[c])
valid++;
}
// 判断左侧窗口是否要收缩
while (right-left>=t.size()) {
//判断是否找到了合法的子串
if(valid==need.size()) return true;
// d 是将移出窗口的字符
char d = s[left];
// 缩小窗口
left++;
// 进行窗口内数据的一系列更新
if (need.count(d)) {
if (window[d] == need[d])
valid--;
window[d]--;
}
}
}
return false;
}
};
问题解决:
错误原因: if(valid=need.size()) 中用了赋值运算符 =，而不是比较运算符 ==，因此这导致了错误的逻辑。
三、找所有字母异位词
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
思路：
这个所谓的字母异位词，不就是排列吗，搞个高端的说法就能糊弄人了吗？相当于，输入一个串 S，一个串 T，找到 S 中所有 T 的排列，返回它们的起始索引。
代码：
class Solution {
public:
vector<int> findAnagrams(string s, string t) {
unordered_map<char, int> need, window;
for (char c : t) {
need[c]++;
}
int left = 0, right = 0;
int valid = 0;
// 记录结果
vector<int> res;
while (right < s.size()) {
char c = s[right];
right++;
// 进行窗口内数据的一系列更新
if (need.count(c)) {
window[c]++;
if (window[c] == need[c]) {
valid++;
}
}
// 判断左侧窗口是否要收缩
while (right - left >= t.size()) {
// 当窗口符合条件时，把起始索引加入 res
if (valid == need.size())
res.push_back(left);
char d = s[left];
left++;
// 进行窗口内数据的一系列更新
if (need.count(d)) {
if (window[d] == need[d]) {
valid--;
}
window[d]--;
}
}
}
return res;
}
};
与找字符串排列一样，只是找到一个合法异位词（排列）之后将其索引加入 res 即可。
四、最长无重复子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
思路:
找到满足条件的子串，更新res为最大子串即可。
代码：
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int left=0,right=0;
unordered_map<char,int> window;
//记录结果
int res=0;
while(right<s.size()){
char c=s[right];
right++;
window[c]++;
//判断是否收缩
while(window[c]>1){
char d=s[left];
left++;
window[d]--;
}
res=max(res,right-left);
}
return res;
}
};
总结：
模版即为：
其中判断左侧是否要收缩时：
判断条件有:
window[c] > 1:最右侧字符有重复就收缩right - left >= t.size():窗口不满足子串t的大小就收缩valid == need.size():已经满足字符个数的个数满了就收缩，使得到最小子串。