#include<bits/stdc++.h>
using namespace std;
const int MAX_CHAR = 256;
string findSubString(const string &str, const string &pat) {
int len1 = str.length();
int len2 = pat.length();
if (len1 < len2) {
return "";
}
int hashPat[MAX_CHAR] = {0};
int hashStr[MAX_CHAR] = {0};
for (int i = 0; i < len2; i++) {
hashPat[pat[i]]++;
}
int start = 0, startIndex = -1, minLength = INT_MAX;
int count = 0;
for (int j = 0; j < len1; j++) {
hashStr[str[j]]++;
if (hashPat[str[j]] != 0 && hashStr[str[j]] <= hashPat[str[j]]) {
count++;
}
if (count == len2) {
while (hashStr[str[start]] > hashPat[str[start]] || hashPat[str[start]] == 0) {
if (hashStr[str[start]] > hashPat[str[start]]) {
hashStr[str[start]]--;
}
start++;
}
int windowLen = j - start + 1;
if (minLength > windowLen) {
minLength = windowLen;
startIndex = start;
}
}
}
if (startIndex == -1) {
return "";
}
return str.substr(startIndex, minLength);
}
int main() {
string str = "ADOBECODEBANC";
string pat = "ABC";
string result = findSubString(str, pat);
cout << "Smallest window containing all characters of the pattern: " << result << endl;
return 0;
}