[V2] 76. Minimum Window SubStrin

最小窗口子串。原题出处：LeetCode 76. Minimum Window Substring
05/08/2020
今天跟朋友做mock interview，他又给我出了这道题，虽然LeetCode提交记录显示我已经做过这道题，但我真的是什么狗屁也想不起来，靠着对sliding window的记忆强做了一次，45分钟之内没有搞出bug free solution。据基友说他面LinkedIn就是做这道题没做出来然后挂了（瑟瑟发抖）。
Mock的时候我试图只用一个HashMap来maintain substring 所需的字符串，但是这样做的话就必须得每次都把Map扫一遍，虽然是常数级别的计算量但也很不优化。时间快到的时候我的基本思路出来了，但是还不能够bug free跑起来，corner case没处理完。这要是Facebook onsite估计肯定挂了吧。
重新看了下LeetCode讨论区，用top voted模板重新写了一遍，使用了一个HashMap来maintain String t的字符和出现次数，然后用counter来track substring是否符合要求。基本原理还是使用双指针，先挪动右指针直到窗口内包含了所有字符，然后再挪动左指针去掉字符，一旦子串不满足条件，就再挪动右指针。
然后发现如果用长度为128的数组来代替HashMap的话运行时间会从7ms降到4ms，代码也会精简不少（毕竟map需要检查有没有key，更新value的时候也比较麻烦）。

class Solution {
    public String minWindow(String s, String t) {
        int [] map = new int[128];
        for (char c : t.toCharArray()) {
          map[c]++;
        }
        int left = 0;
        int right = 0;
        int minLeft = 0;
        int minLen = Integer.MAX_VALUE;
        int counter = t.length();
        while (right < s.length()) {
            char rightCh = s.charAt(right);
            if (map[rightCh] > 0) {
                counter--;
            }
            map[rightCh]--;
            right++;
            while (counter == 0) {
                if (right - left < minLen) {
                    minLen = right - left;
                    minLeft = left;
                }
                char leftCh = s.charAt(left);
                map[leftCh]++;
                if (map[leftCh] > 0) {
                    counter++;
                }
                left++;
              }
        }

        return minLen == Integer.MAX_VALUE ? "" : s.substring(minLeft, minLeft + minLen);
      }
}

在LeetCode讨论区看到了一篇C++模板，我来把它翻译成Java：

int findSubstring(String s){
        Map<Character, Integer> map = new HashMap<>(); // 用Map或者是长度为256的char array都可以，问题不大
        int counter = 0; // check whether the substring is valid
        int begin=0, end=0; //two pointers, one point to tail and one  head
        int d =  Integer.MAX_VALUE; //the length of substring

        for() { 
          /* initialize the hash map here */ 
        }

        while(end < s.length()){

            if(map.get(s.charAt(end++))-- ?) {  /* modify counter here */ }

            while(/* counter condition */){ 
                 
                 /* update d here if finding minimum*/

                //increase begin to make it invalid/valid again
                
                if(map.get(s.charAt(begin++))++ ?){ /*modify counter here*/ }
            }  

            /* update d here if finding maximum*/
        }
        return d;
  }

我原来的naive版本，用了两个HashMap:

/**
 * 可以用HashMap，也可以用长度为128的数组来存储字符的出现次数(char ASCII - int 互转)
 * 同向双指针(sliding window)
 * Similar to 438 https://leetcode.com/problems/find-all-anagrams-in-a-string/ 
 * Runtime: 14 ms, faster than 40.32% of Java online submissions for Minimum Window Substring.
 * Memory Usage: 40.4 MB, less than 24.47% of Java online submissions for Minimum Window Substring.
 * 10 minute. Minor bug.
 */
class Solution {
    public String minWindow(String s, String t) {
        String result = "";
        if (s == null || s.length() == 0 || s.length() < t.length()) {
            return result;
        }
        Map<Character, Integer> mapT = new HashMap<>();
        Map<Character, Integer> mapS = new HashMap<>();
        for (Character c : t.toCharArray()) {
            mapT.put(c, mapT.getOrDefault(c, 0) + 1);
        }
        int left = 0;
        int right = 0;
        int match = 0;
        int minLen = Integer.MAX_VALUE;
        for (; right < s.length(); right++) {
            Character rightChar = s.charAt(right);
            if (mapT.containsKey(rightChar)) {
                mapS.put(rightChar, mapS.getOrDefault(rightChar, 0) + 1);
                
                if (mapT.get(rightChar).equals(mapS.get(rightChar))) {
                    match++;
                }
            }
            
            while (mapT.keySet().size() == match) {
                if (right - left + 1 < minLen) {
                    result = s.substring(left, right + 1);
                    minLen = right - left + 1;
                }
                
                // Move left pointer to the right;
                Character leftChar = s.charAt(left);
                if (mapT.containsKey(leftChar)) {
                    mapS.put(leftChar, mapS.get(leftChar) - 1);
                    if (mapS.get(leftChar) < mapT.get(leftChar)) {
                        match--;
                    }
                }
                left++;
            }
        }
        
        return result;
    }
}