Minimum Window Substring leetcode solution

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 endstart+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;
}

Resolving technical problems:

Solve your technical problems instantly

We provide Remote Technical Support from Monday to Sunday, 7:00PM to 1:00 AM

Mail your problem details at writeulearn@gmail.com along with your mobile numberand we will give you a call for further details. We usually attend your problems within 60 minutes and solve it in maximum 2 days.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.