lc-76

//Given two strings s and t of lengths m and n respectively, return the minimum 
//window substring of s such that every character in t (including duplicates) is i
//ncluded in the window. If there is no such substring, return the empty string ""
//. 
//
// The testcases will be generated such that the answer is unique. 
//
// A substring is a contiguous sequence of characters within the string. 
//
// 
// Example 1: 
//
// 
//Input: s = "ADOBECODEBANC", t = "ABC"
//Output: "BANC"
//Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' fr
//om string t.
// 
//
// Example 2: 
//
// 
//Input: s = "a", t = "a"
//Output: "a"
//Explanation: The entire string s is the minimum window.
// 
//
// Example 3: 
//
// 
//Input: s = "a", t = "aa"
//Output: ""
//Explanation: Both 'a's from t must be included in the window.
//Since the largest window of s only has one 'a', return empty string.
// 
//
// 
// Constraints: 
//
// 
// m == s.length 
// n == t.length 
// 1 <= m, n <= 105 
// s and t consist of uppercase and lowercase English letters. 
// 
//
// 
//Follow up: Could you find an algorithm that runs in O(m + n) time? Related Top
//ics Hash Table String Sliding Window 
// 👍 11543 👎 553


import java.util.HashMap;
import java.util.Map;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public String minWindow(String s, String t) {
        if (s == null || s.length() == 0 || t == null || t.length() == 0) {
            return "";
        }

        int bestStart = 0, left = 0, right = 0, matchNum = 0, length = Integer.MAX_VALUE;

        Map<Character, Integer> curMap = new HashMap<>();
        Map<Character, Integer> neededMap = new HashMap<>();


        for (char ch : t.toCharArray()) {
            neededMap.putIfAbsent(ch, 0);
            neededMap.put(ch, neededMap.get(ch) + 1);
        }

        while (right < s.length()) {
            char ch = s.charAt(right);

            if (neededMap.containsKey(ch)) {
                curMap.putIfAbsent(ch, 0);
                int cur = curMap.get(ch);
                cur++;
                curMap.put(ch, cur);

                if (cur == neededMap.get(ch)) {
                    matchNum++;
                }
            }

            while (matchNum == neededMap.size()) {
                if (right - left < length) {
                    length = right - left + 1;
                    bestStart = left;
                }

                char curCh = s.charAt(left);

                if (curMap.containsKey(curCh)) {
                    curMap.put(curCh, curMap.get(curCh) - 1);

                    if (curMap.get(curCh) < neededMap.get(curCh)) {
                        matchNum--;
                    }
                }

                left++;
            }

            right++;
        }

        return length == Integer.MAX_VALUE ? "" : s.substring(bestStart, bestStart + length);

    }
}
//leetcode submit region end(Prohibit modification and deletion)