[LeetCode]Minimum Window Substring

和substring with concatenation of all words类似的解法，仍然是双指针的，维护basemap和currmap和一个counter，但是指针移动的策略略有不同，在之前一题中，我们找的是一块区域，区域里面是有string array里所有的string组成的，也就是说不允许不在array里的string出现，也不许超出数量的string存在。但是在这一题中，根据题意，不在T里面的字符也是可以出现的，而且也容许超出某个字符在T里面数量的字符出现。所以根据右指针的移动，左指针移动的策略是：

• 如果right指向的字符不在T里，什么也不做
• 如果right指向的字符在T里，更新currmap，如果char c在currmap里的数量小于basemap，count++，如果count > T.length()，右移左指针，移动左指针的条件是，如果left指向的字符不在T里或者currmap里的数量超了basemap中的数量，就左移，直到停下为止，同时注意更新currmap，之后看情况更新应该返回的结果，然后为了让程序可以继续正确地进行下去，我们在左移left一位，使得count--，类似回到右移左指针之前的情况，然后更新map

每个char被扫2次，时间复杂度O(n)，代码如下：

	public class Solution {
	public String minWindow(String S, String T) {
	if (S == null || T == null)
	return "";
	int len1 = S.length(), len2 = T.length();
	if (len2 > len1)
	return "";
	HashMap<Character, Integer> baseMap = new HashMap<Character, Integer>();
	for (int i = 0; i < len2; i++) {
	if (!baseMap.containsKey(T.charAt(i)))
	baseMap.put(T.charAt(i), 1);
	else
	baseMap.put(T.charAt(i), baseMap.get(T.charAt(i)) + 1);
	}
	HashMap<Character, Integer> currMap = new HashMap<Character, Integer>();
	int count = 0, left = 0, min = Integer.MAX_VALUE, start = -1;
	for (int right = 0; right < len1; right++) {
	char curr = S.charAt(right);
	if (baseMap.containsKey(curr)) {
	if (!currMap.containsKey(curr))
	currMap.put(curr, 1);
	else
	currMap.put(curr, currMap.get(curr) + 1);
	if (currMap.get(curr) <= baseMap.get(curr))
	count++;
	//move left pointer as right as possible
	if (count == len2){
	//discard redundant chars
	while(!currMap.containsKey(S.charAt(left)) || currMap.get(S.charAt(left)) > baseMap.get(S.charAt(left))) {
	if(currMap.containsKey(S.charAt(left))) {
	currMap.put(S.charAt(left), currMap.get(S.charAt(left)) - 1);
	if (currMap.get(S.charAt(left)) == 0)
	currMap.remove(S.charAt(left));
	}
	left++;
	}
	if (right - left + 1 < min) {
	min = right - left + 1;
	start = left;
	}
	//move left one step, continue
	currMap.put(S.charAt(left), currMap.get(S.charAt(left)) - 1);
	if (currMap.get(S.charAt(left)) == 0)
	currMap.remove(S.charAt(left));
	left++;
	count--;
	}
	}
	}
	return start == -1? "": S.substring(start, start + min);
	}
	}

view raw Minimum Window Substring.java hosted with ❤ by GitHub