C ++中的最小窗口子字符串
假设我们有一个字符串S和T。我们必须在S中找到将包含T中所有字符的最小窗口。因此，如果输入类似于“ABHDAXCVBAGTXATYCB”和T=“ABC”，那么结果将是：CVBA”。
为了解决这个问题，我们将遵循以下步骤-
创建一张映射
将x的频率存储到m
长度：=s的大小，左：=0，右：=0，ansLeft：=0和ansRight：=0
counter：=x的大小，flag：=false，ans：=空字符串
而高度<s的大小-
如果是右–左+1<=长度
如果left=right，则打破循环
c：=s[左]
如果c存在于m中，则将m[c]加1
如果m[c]>0，则将计数器增加1
向左增加1
长度：=右–左+1
标志：=true
ansLeft：=左，ansRight：=右
如果m[c]>0，则将计数器减1
将m[c]减少1
c：=s[正确]
如果c存在于m中，则
而counter=0且左<=右
向右增加1
如果flag为false，则返回ans
否则，对于范围在ansLeft至ansRight中的i，将ans增加s[i]
返回ans
示例
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string minWindow(string s, string x) {
map <char, int> m;
for(int i =0;i<x.size();i++)m[x[i]]++;
int length = s.size();
int left = 0, right = 0 , ansLeft = 0, ansRight = 0;
int counter = x.size();
bool flag = false;
string ans = "";
while(right<s.size()){
char c = s[right];
if(m.find(c)!=m.end()){
if(m[c]>0)counter--;
m[c]--;
}
while(counter == 0 && left<=right){
if(right-left+1 <=length){
length = right-left+1;
flag = true;
ansLeft = left;
ansRight = right;
}
if(left == right)break;
c = s[left];
if(m.find(c)!=m.end()){
m[c]++;
if(m[c]>0)counter++;
}
left++;
}
right++;
}
if(!flag)return ans;
else
for(int i =ansLeft;i<=ansRight;i++)ans+=s[i];
return ans;
}
};
main(){
Solution ob;
cout << (ob.minWindow("ABHDAXCVBAGTXATYCB", "ABC"));
}输入值
"ABHDAXCVBAGTXATYCB" "ABC"
输出结果
CVBA