Minimum Window Substring @LeetCode

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.

	package leetcode.slidingWindow;
	import java.util.HashMap;
	/**
	* Solution: Sliding Window. Create a dict, and maintain a window include all T chars.
	* 跟longest substring 题目区别是，这里不在字典里得char，也可能是答案的一部分，所以策略是
	* 1.碰到dict没有的，相当于continue，窗口继续右移， 遇到dict中的，hashMap value-1
	* 2.全部包含以后，移动窗口leftBound,
	* 如果是不在dict中的无用字符，leftBound+1
	* 如果是dict中的重复的无用字符，比如 AADOBEC. 因为window rightBound 右移过程中 -1，现在 +1 补回来，如果这样 value <= 0. 不进入step3.
	* 如果是dict中的字符，比如 ADOBEC, +1后应该value>0. 此时，[leftBound, i] 构成一组解，计算一下minLength.
	* 3. 够成一组解后，leftBound++, 此时没有全部包含，又回到step 1. 直到end.
	*
	* 什么时候全部包含了呢？
	* hashMap的所有key对应value全部 <= 0 的时候，这个处理太麻烦，我们用一个count来标记T length(). 每次碰见dict时候+1.
	*
	* Referenece: http://codeganker.blogspot.com/2014/03/minimum-window-substring-leetcode.html
	* 他的Blog非常棒，赞一个！
	* @author jeffwan
	* @date Apr 12, 2014
	*/
	public class MinWindow {
	public String minWindow(String S, String T) {
	if (S == null || T == null || S.length() == 0 || T.length() == 0) {
	return "";
	}
	// Store all character in T to HashMap. there may have duplicates.
	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 count = 0; // T char count
	int leftBound = 0;
	String result = "";
	int minLength = S.length() + 1;
	for (int i = 0; i < S.length(); i++) {
	if (map.containsKey(S.charAt(i))) {
	map.put(S.charAt(i), map.get(S.charAt(i)) - 1);
	if (map.get(S.charAt(i)) >= 0) {
	count++;
	}
	// Window contains all chars in T.
	while (count == T.length()) {
	if (map.containsKey(S.charAt(leftBound))) {
	map.put(S.charAt(leftBound), map.get(S.charAt(leftBound)) + 1);
	// that means S.charAt(leftBound) is the most left char in T of this window.
	if (map.get(S.charAt(leftBound)) > 0) {
	if (minLength > i - leftBound + 1) {
	result = S.substring(leftBound, i + 1);
	minLength = i - leftBound + 1;
	}
	count--;
	}
	}
	leftBound++;
	}
	}
	}
	return result;
	}
	}

view raw MinWindow.java hosted with ❤ by GitHub