#include <iostream>
#include <unordered_map>
using namespace std;
string minWindow(string s, string t) {
unordered_map<char, int> need, window; // 分别记录需要的字符和窗口中的字符
for (char c : t) need[c]++; // 统计需要的字符
int left = 0, right = 0; // 左右指针
int valid = 0; // 记录窗口中满足need条件的字符个数
int start = 0, len = INT_MAX; // 记录最小覆盖子串的起始位置和长度
while (right < s.size()) { // 移动右指针
char c = s[right];
right++; // 右移窗口
if (need.count(c)) { // 如果该字符是需要的
window[c]++; // 放入窗口
if (window[c] == need[c]) // 如果已经满足need条件
valid++; // valid加1
}
while (valid == need.size()) { // 如果窗口中包含了所有需要的字符
if (right - left < len) { // 更新最小覆盖子串的位置和长度
start = left;
len = right - left;
}
char d = s[left]; // 左指针向右移动
left++;
if (need.count(d)) { // 如果该字符是需要的
if (window[d] == need[d]) // 如果窗口中该字符数量已经等于need中数量
valid--; // valid减1
window[d]--; // 从窗口中移除该字符
}
}
}
return len == INT_MAX ? "" : s.substr(start, len); // 返回最小覆盖子串
}
int main() {
string s = "ADOBECODEBANC";
string t = "ABC";
cout << minWindow(s, t) << endl; // 输出：BANC
return 0;
}
本站部分文章来源于网络，版权归原作者所有，如有侵权请联系站长删除。
转载请注明出处：https://sdn.0voice.com/?id=168
![0% [Connecting to archive.ubuntu.com (2620:2d:4000:1::103)]](https://linuxcpp.0voice.com/zb_users/upload/2023/05/202305162216033652866.png)
