[Geeks for Geeks] Smallest window in a string containing all the characters of another string

Smallest window in a string containing all the characters of another string

Given two strings S and P. Find the smallest window in the string S consisting of all the characters(including duplicates) of the string P. Return “-1” in case there is no such window present. In case there are multiple such windows of same length, return the one with the least starting index.

  • Time : O(n)
  • Space : O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
//Function to find the smallest window in the string s consisting
//of all the characters of string p.
string smallestWindow(string s, string p) {
unordered_map<char, int> counter;
unordered_map<char, int> sCounter;
for(auto& ch : p)
counter[ch]++;
int freq = counter.size(), res = INT_MAX, pos;
int l = 0, r = 0, n = s.length();
while(r < n) {
while(r < n and freq) {
if(counter.count(s[r])) {
if(counter[s[r]] == ++sCounter[s[r]]) freq--;
}
r++;
}
while(l < r and !freq) {
if(res > r - l) {
res = r - l; pos = l;
}
if(counter.count(s[l])) {
if(counter[s[l]] == sCounter[s[l]]--) freq++;
}
l++;
}
}

return res == INT_MAX ? "-1" : s.substr(pos, res);
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/05/22/PS/GeeksforGeeks/smallest-window-in-a-string-containing-all-the-characters-of-another-string/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.