76. Minimum Window Substring (sliding window)

use two pointers (sliding window)

T :O(m+n)

S: O(|target|+|source|)

class Solution {
    public String minWindow(String s, String t) {
        int n = s.length();
        Map<Character, Integer> sCounter = new HashMap<>(); // char, count
        Map<Character, Integer> tCounter = new HashMap<>(); // char, count
        
        // record target char, freq
        for (char c : t.toCharArray()) {
            tCounter.put(c, tCounter.getOrDefault(c, 0)+1);
        }

        int end = 0;
        int charMatchedNum = 0;
        int resStart = 0;
        int resLen = Integer.MAX_VALUE; // for mini len result
        for (int start = 0; start < n; start++) {
            while (end < n && charMatchedNum < tCounter.size()) {
                char c = s.charAt(end);
                sCounter.put(c, sCounter.getOrDefault(c, 0)+1); // record source char, freq
                
                // needs integer to int, unboxing not work
                if ((int)sCounter.get(c) == (int)tCounter.getOrDefault(c,0)) { // if char freq equals, find matched
                    charMatchedNum++;
                }
                end++;
            }

            if (charMatchedNum == tCounter.size()) { // if matched count == target freq count, can get a result
                if (resLen > end - start) { // but we want mini len of result
                    resStart = start; // result's start index
                    resLen = end - start; // result's len
                }
            }
            
            char c = s.charAt(start);
            sCounter.put(c, sCounter.getOrDefault(c,0)-1); // out of the start index loop, 
            
            // 如果兩者減1後, 相等, matched count應該 --
            if ((int)sCounter.get(c) == (int)(tCounter.getOrDefault(c,0) - 1)) { 
                charMatchedNum--;
            }
        }
        // 如果 resLen 還是最大值, 代表找不到
        return resLen == Integer.MAX_VALUE ? "" : s.substring(resStart, resStart + resLen);
    }
}

T: O(n)
S: O(n)

class Solution {
    public String minWindow(String s, String t) {
        if (t.length() > s.length()) {
            return "";
        }
        
        int len = Integer.MAX_VALUE;
        int left = 0;
        int right = 0;
        int start = 0;
        
        Map<Character, Integer> needs = new HashMap<>();
        int matched = 0;
        for (char c : t.toCharArray()) {
            needs.put(c, needs.getOrDefault(c, 0)+1);
        }
        
        while (right < s.length()) {
            char rightChar = s.charAt(right);
            right++;
            if (needs.containsKey(rightChar)) {
                needs.put(rightChar, needs.getOrDefault(rightChar, 0)-1);
                if (needs.get(rightChar) == 0) {
                    matched++;
                }
            }
            while (matched == needs.size()) {
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }
                
                char leftChar = s.charAt(left);
                left++;
                if (needs.containsKey(leftChar)) {
                    if (needs.get(leftChar) == 0) {
                        matched--;
                    }
                    needs.put(leftChar, needs.getOrDefault(leftChar, 0)+1);
                }
            }
        }

        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }
}
/*
build a t map
compare in s, s map record in this window, do we have t map count
s = "ADOBECODEBANC", t = "ABC"
      l
          r
          
          when we have all valid count, start to shrink left, 
          update min len, record start point(left) -> right - left
          until not valid number
          
          count must be the same (or "aa" , "aa", the ans -> "a" only one)
          
          at last, just use one map, to save needs count first,
          then using subtraction (if current char == needs word, subtrct needs count), when needs == 0, matched++
          if matched == needs.size() it means we have find matched substring contains all needs words (t)
          
          T: O(n)
          S: O(n)
*/