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