Sliding Window - 76. Minimum Window Substring

76. 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).

Example:

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

Note:

• If there is no such window in S that covers all characters in T, return the empty string "".
• If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

思路：

这是一道经典的sliding window的题目，题目意思是给定两个字符串，字符串S如果包含另一个字符串T的所有字符，那么就返回这个包含T所有字符的最小字符串。做法是使用two points，来找到合法的子串，然后从左边不断收缩合法字串的大小，直到合法性消失之后，快指针继续往后探索寻找合法子串。因为字符串中只包含字符，所以可以把map改用256位的数组来记录t中的字符。

代码：

java：

class Solution {

   /* public String minWindow(String s, String t) {

        // corner case
        if (s.length() < t.length()) return "";
        
        // gen string t map
        Map<Character, Integer> wordDict = new HashMap<>();
        for (char c : t.toCharArray()){
            Integer count = wordDict.get(c);
            if (count == null) {
                wordDict.put(c, 1);
            } else {
                wordDict.put(c, count+1);
            }
        }
        
        int slow = 0, minLen = Integer.MAX_VALUE, matchCount = 0, index = 0;
        for (int fast = 0; fast < s.length(); fast++) {
            char c = s.charAt(fast);
            Integer count = wordDict.get(c);
            if (count == null) continue;
            
            wordDict.put(c, count-1);
            // macth another character
            if (count == 1) matchCount++; // 如果count减少，就说明找到一个匹配的字符。
            
            // 如果发现找到了t中所有的字符，就开始逐步从子串最左边开始往右移动，缩短匹配字符串的长度。
            while (matchCount == wordDict.size()) {
                // find a valid substring
                if (fast - slow + 1 < minLen) {
                    minLen = fast - slow + 1;
                    index = slow;
                }
                char leftmost = s.charAt(slow++);
                Integer leftmostCount = wordDict.get(leftmost);
                if (leftmostCount == null) continue;  // 如果是t中没有的字符就不管
                
                // 如果找t中有的字符，就把map中的值加一
                wordDict.put(leftmost, leftmostCount + 1);
                if (leftmostCount == 0) matchCount--; // 0->1
            }
        } 
        
        return minLen == Integer.MAX_VALUE ? "" : s.substring(index, index + minLen); 
    }*/
    
    public String minWindow(String s, String t) {
        // corner case
        if (s.length() < t.length()) return "";
        
        // gen string t map
        int[] wordDict = new int[256];
        for (char c : t.toCharArray()) wordDict[c]++;
           
        
        int slow = 0, minLen = Integer.MAX_VALUE, matchCount = t.length(), index = 0;
        for (int fast = 0; fast < s.length(); fast++) {
            char c = s.charAt(fast);
            // 在数组中发现一位大于0，就说明找到了一个t中的字符，matchCount减一
            if (wordDict[c] > 0) matchCount--;
            // 如果不是t中的字符就把数组中的数组减一
            wordDict[c]--;        
            
            // 如果发现找到了t中所有的字符，就开始逐步从子串最左边开始往右移动，缩短匹配字符串的长度。
            while (matchCount == 0) {
                // find a valid substring
                if (fast - slow + 1 < minLen) {
                    minLen = fast - slow + 1;
                    index = slow;
                }
                
                // 逐步从子串最左边开始往右移动，缩短匹配字符串的长度。
                char leftmost = s.charAt(slow++);
                // 然后把数组的c增加，如果发现增加之后大于0，说明又找到一个t满足的字符
                wordDict[leftmost]++;
                if (wordDict[leftmost] > 0)  matchCount++;
            }
        } 
        
        return minLen == Integer.MAX_VALUE ? "" : s.substring(index, index + minLen); 
    }
}