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.
注意：如果一个字母在T中出现了k次，那么在窗口中该字母至少出现k次
Solution:
这道题是字符串处理的题目，和Substring with Concatenation of All Words思路非常类似，同样是建立一个字典，然后维护一个窗口。区别是在这道题目中，因为可以跳过没在字典里面的字符（也就是这个串不需要包含且仅仅包含字典里面的字符，有一些不在字典的仍然可以满足要求），所以遇到没在字典里面的字符可以继续移动窗口右端，而移动窗口左端的条件是当找到满足条件的串之后，一直移动窗口左端直到有字典里的字符不再在窗口里。在实现中就是维护一个HashMap，一开始key包含字典中所有字符，value就是该字符的数量，然后遇到字典中字符时就将对应字符的数量减一。算法的时间复杂度是O(n),其中n是字符串的长度，因为每个字符再维护窗口的过程中不会被访问多于两次。空间复杂度则是O(字典的大小)，也就是代码中T的长度。
这个方法在Substring with Concatenation of All Words和Longest Substring Without Repeating Characters中都介绍过，属于一种类型的题目，只要掌握了思路便可以举一反三，都可以将这类问题降低到线性复杂度。
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[128];
int[] hasFound = new int[128];
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