Minimum Window Substring leetcode solution

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example,
S = “ADOBECODEBANC”
T = “ABC”
Minimum window is “BANC”.

Note:
If there is no such window in S that covers all characters in T, return the emtpy string “”.
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

We are required to implement a O(n) algorithm. We can achieve it by using two pointers. We will use pointer “start” and pointer “end”, which indicates the substring we are processing.

Firstly, we will move the “end” pointer right, until we find all characters. But how can we know that we have found all the characters? There may be duplicate characters in string T. So  use a HashMap to save the number of each characters in string T. Another HashMap is used to save the number of characters found. When we move pointer “end”, we will check if the number of this character is smaller than we need to found. If it is, we will increase one to a total counter and increase one to the number of this character. Otherwise only the number of this character is increased.

When the total counter equals to length of T, we know that we have found all characters. Now we can move the “start” pointer as right as possible. We can move it when it pointing to a character that is not in T, or even it is in T, but the number of this character is larger than the number we need to find. In other words, we move “start” pointer when the substring from “start” to “end” does contains all characters in T.

We can compare the value end–start+1, which is the length of a substring that contains all characters in T, to the minimum length. If it’s shorter, we can update the minimum length.

string minWindow(string S, string T) {

unordered_map<char, int> dict;

//adding T to a hashmap counting number of each char
for (int i = 0; i < T.length(); i++) {
char c = T[i];
if (dict.find(c) == dict.end())
dict[c]= 1;
else
dict[c] ++;
}
unordered_map<char, int> found ; // hashmap of found word char
int foundCounter = 0;
int start = 0;
int end = 0;
int min = INT_MAX;
string minWindow = “”;
while (end < S.length()) {
char c = S[end];
if (dict.find(c) !=dict.end()) { //If found c in T HashMap
if (found.find(c) !=found.end()) { // If found c in found word HashMap
if (found[c] < dict[c]) // If num of char is less in found word then in T
foundCounter++;
found[c]= found[c] + 1; //increment char  count in found hashmap
} else {
found[c]= 1;
foundCounter++;
}
}
if (foundCounter == T.length()) {
//When foundCounter equals to T.length(), in other words, found all characters.
char sc = S[start];

//while S start char is not found in found hashmap or its count is > than T hashmap
while ((found.find(sc)==found.end()) || found[sc] > dict[sc]) {

// If S start char is found in found hashmap and its count is > than T hashmap
if ((found.find(sc) !=found.end()) && found[sc] > dict[sc])
found[sc] — ;
start++; // move start
sc = S[start];
}
if (end – start + 1 < min) {
minWindow = S.substr(start, end + 1-start);
min = end – start + 1;
}
}
end++;
}
return minWindow;
}