Trouvez la plus petite fenêtre d'une chaîne contenant tous les caractères d'une autre chaîne
#include <bits/stdc++.h>
using namespace std;
// Function
string Minimum_Window(string s, string t)
{
int m[256] = { 0 };
// Answer
int ans = INT_MAX; // length of ans
int start = 0; // starting index of ans
int count = 0;
// creating map
for (int i = 0; i < t.length(); i++) {
if (m[t[i]] == 0)
count++;
m[t[i]]++;
}
// References of Window
int i = 0;
int j = 0;
// Traversing the window
while (j < s.length()) {
// Calculations
m[s[j]]--;
if (m[s[j]] == 0)
count--;
// Condition matching
if (count == 0) {
while (count == 0) {
// Sorting ans
if (ans > j - i + 1) {
ans = min(ans, j - i + 1);
start = i;
}
// Sliding I
// Calculation for removing I
m[s[i]]++;
if (m[s[i]] > 0)
count++;
i++;
}
}
j++;
}
if (ans != INT_MAX)
return s.substr(start, ans);
else
return "-1";
}
main()
{
string s = "ADOBECODEBANC";
string t = "ABC";
cout<<"-->Smallest window that contain all character : "<<endl;
cout << Minimum_Window(s, t);
}
