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

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.

解题： 找最小子串，和find all anagrams同样的解题思路，只是end的结束条件变了。 首先我们定义sMap,tMap来存字符count， 当子串没有所有t的字符时，我们就把当前字符的sMap的count加一，直到我们找到一个valid substring或者到达字符串最后结束。 当我们找到一个valid substring，我们就更新minstr 和count。

class Solution {
    public String minWindow(String s, String t) {
        String minStr = "";
        int count = Integer.MAX_VALUE;
        int[] sMap = new int[256];
        int[] tMap = new int[256];

        //initilize tMap with character count
        for (int i = 0; i < t.length(); i++) {
            tMap[t.charAt(i)]++;
        }

        int start = 0, end = 0;
        for ( start = 0; start < s.length(); start++) {
            //if current substring does not contain all the characters from t, end ++
            while (!isValid(sMap, tMap) && end < s.length()) {
                sMap[s.charAt(end)]++;
                //keep adding end util we find a matched substring or to the end
                if (end < s.length()) {
                    end++;
                } else {
                   break; 
                }
            } 

            //if current string contains all the characters 
            if (isValid(sMap, tMap)) {
                if (count > end - start) {
                    minStr = s.substring(start, end);
                    count = end - start;
                }
            }
            sMap[s.charAt(start)]--;
        }
        return minStr;
    }

    public boolean isValid(int[] sMap, int[] tMap) {
        for (int i = 0; i < 256; i++) {
            if (sMap[i] < tMap[i]) return false;
        }
        return true;
    }
}