# Minimum Window Substring

https://leetcode.com/problems/minimum-window-substring/

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 empty string "".

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

Solution:

http://blog.csdn.net/linhuanmars/article/details/20343903

``````public String minWindow(String S, String T) {
if(S==null || S.length()==0)
return "";
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
for(int i=0; i<T.length();i++)
{
if(map.containsKey(T.charAt(i)))
{
map.put(T.charAt(i),map.get(T.charAt(i))+1);
}
else
{
map.put(T.charAt(i),1);
}
}
int left = 0;
int count = 0;
int minLen = S.length()+1;
int minStart = 0;
for(int right=0; right<S.length();right++)
{
if(map.containsKey(S.charAt(right)))
{
map.put(S.charAt(right),map.get(S.charAt(right))-1);
if(map.get(S.charAt(right))>=0)
{
count++;
}
while(count == T.length())
{
if(right-left+1<minLen)
{
minLen = right-left+1;
minStart = left;
}
if(map.containsKey(S.charAt(left)))
{
map.put(S.charAt(left), map.get(S.charAt(left))+1);
if(map.get(S.charAt(left))>0)
{
count--;
}
}
left++;
}
}
}
if(minLen>S.length())
{
return "";
}
return S.substring(minStart,minStart+minLen);
}
``````

Solution II:

Notice how complicated the above solution is. It uses a hash table, a queue, and a sorted map. During an interview, the problems tend to be short and the solution usually can be coded in about 50 lines of code. So be sure that you say out loud what you are thinking and keep communication opened with the interviewer. Check if your approach is unnecessary complex, he/she might be able to give you guidance. The last thing you want to do is to get stuck in a corner and keep silent.

To help illustrate this approach, I use a different example: S = “acbbaca” and T = “aba“. The idea is mainly based on the help of two pointers (begin and end position of the window) and two tables (needToFind and hasFound) while traversing S. needToFind stores the total count of a character in T and hasFound stores the total count of a character met so far. We also use a count variable to store the total characters in T that’s met so far (not counting characters where hasFound[x] exceeds needToFind[x]). When count equals T‘s length, we know a valid window is found.

Each time we advance the end pointer (pointing to an element x), we increment hasFound[x] by one. We also increment count by one if hasFound[x] is less than or equal to needToFind[x]. Why? When the constraint is met (that is, count equals to T‘s size), we immediately advance begin pointer as far right as possible while maintaining the constraint.

How do we check if it is maintaining the constraint? Assume that begin points to an element x, we check if hasFound[x] is greater than needToFind[x]. If it is, we can decrement hasFound[x] by one and advancing begin pointer without breaking the constraint. On the other hand, if it is not, we stop immediately as advancing begin pointer breaks the window constraint.

Finally, we check if the minimum window length is less than the current minimum. Update the current minimum if a new minimum is found.

Essentially, the algorithm finds the first window that satisfies the constraint, then continue maintaining the constraint throughout.

``````public class Solution {
public String minWindow(String S, String T) {
HashMap<Character, Integer> dict = new HashMap<>();
for (int i = 0; i < T.length(); i++) {
char c = T.charAt(i);
if (!dict.containsKey(c))
dict.put(c, 1);
else
dict.put(c, dict.get(c) + 1);
}
HashMap<Character, Integer> found = new HashMap<>();
int foundCounter = 0;
int start = 0;
int end = 0;
int min = Integer.MAX_VALUE;
String minWindow = "";
while (end < S.length()) {
char c = S.charAt(end);
if (dict.containsKey(c)) {
if (found.containsKey(c)) {
if (found.get(c) < dict.get(c))
foundCounter++;
found.put(c, found.get(c) + 1);
} else {
found.put(c, 1);
foundCounter++;
}
}
if (foundCounter == T.length()) {
//When foundCounter equals to T.length(), in other words, found all characters.
char sc = S.charAt(start);
while (!found.containsKey(sc) || found.get(sc) > dict.get(sc)) {
if (found.containsKey(sc) && found.get(sc) > dict.get(sc))
found.put(sc, found.get(sc) - 1);
start++;
sc = S.charAt(start);
}
if (end - start + 1 < min) {
minWindow = S.substring(start, end + 1);
min = end - start + 1;
}
}
end++;
}
return minWindow;
}
}
``````

Solution III: O(1) space

``````public class Solution {
public String minWindow(String S, String T) {
if (S.length() == 0 || T.length() == 0 || S.length() < T.length()) {
return "";
}

int[] needToFind = new int;
int[] hasFound = new int;

for (char c : T.toCharArray()) {
needToFind[c]++;
}

int count = 0, minWindowLen = S.length()+1;
int minWindowBegin = 0, minWindowEnd = 0;

int begin = 0, end = 0;

for (end = 0; end < S.length(); end++) {
// skip characters not in T
if (needToFind[S.charAt(end)] == 0) continue;
hasFound[S.charAt(end)]++;
if (hasFound[S.charAt(end)] <= needToFind[S.charAt(end)])
count++;

// if window constraint is satisfied
if (count == T.length()) {
// advance begin index as far right as possible,
// stop when advancing breaks window constraint.
while (needToFind[S.charAt(begin)] == 0 ||
hasFound[S.charAt(begin)] > needToFind[S.charAt(begin)]) {
if (hasFound[S.charAt(begin)] > needToFind[S.charAt(begin)])
hasFound[S.charAt(begin)]--;
begin++;
}

// update minWindow if a minimum length is met
int windowLen = end - begin + 1;
if (windowLen < minWindowLen) {
minWindowBegin = begin;
minWindowEnd = end;
minWindowLen = windowLen;
} // end if
} // end if
} // end for

if (minWindowLen == S.length()+1) {
return "";
}
return S.substring(minWindowBegin, minWindowEnd+1);
}
}
``````

ref:

http://articles.leetcode.com/2010/11/finding-minimum-window-in-s-which.html