76. Minimum Window Substring

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 included in the window. If there is no such substring, return the empty string "".

The testcases will be generated such that the answer is unique.

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from 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?

Solution:

class Solution {
    public String minWindow(String s, String t) {
        if (s.length() < t.length()){
            return "";
        }

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

        for (int i = 0; i < t.length(); i++){
            map.put(t.charAt(i), map.getOrDefault(t.charAt(i), 0) + 1);
        }

        int slow = 0;
        int count = t.length();
        int startInd = 0;
        int minLength = Integer.MAX_VALUE;

        for (int fast = 0; fast < s.length(); fast++){
            char curFast = s.charAt(fast);

            if (map.containsKey(curFast)){
                int curFastCount = map.get(curFast);
                if (curFastCount > 0){
                    count--;
                }

                map.put(curFast, curFastCount - 1);
            }

            while(count == 0){
                if (fast - slow + 1 <= minLength){
                    minLength = fast - slow + 1;
                    startInd = slow;

                }

                if (!map.containsKey(s.charAt(slow))){
                    slow++;
                }else{
                    if (map.get(s.charAt(slow)) == 0){
                        count++;
                    }

                    map.put(s.charAt(slow), map.get(s.charAt(slow)) + 1);
                    slow++;
                }
            }
        }

        if (minLength == Integer.MAX_VALUE){
            return "";
        }else{
            return s.substring(startInd, startInd + minLength);
        }
    }
}

// TC: O(m + n)
// SC: O(n) -> O(1) 

class Solution {
    public String minWindow(String s, String t) {
        if (s.length() < t.length()){
            return "";
        }

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

        int slow = 0;
        int fast = 0;
        int minLength = Integer.MAX_VALUE;
        int count = t.length();
        int startInd = 0;

        for (int i = 0; i < t.length(); i++){
            map.put(t.charAt(i), map.getOrDefault(t.charAt(i), 0) + 1);
        }

        while(fast < s.length()){
            char curFast = s.charAt(fast);
            if (map.containsKey(curFast)){
                int curFastCount = map.get(curFast);
                if (curFastCount > 0){
                    count--;
                }

                map.put(curFast, curFastCount - 1);
            }

            fast++;

            while(count == 0){

                if (fast - slow < minLength){
                    minLength = fast - slow;
                    startInd = slow;
                }

                char curSlow = s.charAt(slow);
                if (!map.containsKey(curSlow)){
                    slow++;
                }else {
                    // contains
                    int curSlowCount = map.get(curSlow);
                    if (curSlowCount == 0){
                        count++;
                    }
                    map.put(curSlow, curSlowCount + 1);

                    slow++;
                }
            }
        }

        if (minLength == Integer.MAX_VALUE){
            return "";
        }else{
            return s.substring(startInd, startInd + minLength);
        }
    }
}

class Solution {
    public String minWindow(String s, String t) {
        if (t.length() > s.length()){
            return "";
        }

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

        for (int i = 0; i < t.length(); i++){
            freq.put(t.charAt(i), freq.getOrDefault(t.charAt(i), 0) + 1);
        }

        int slow = 0;
        int fast = 0; 
        int count = t.length();
        int minLength = Integer.MAX_VALUE;

        int startInd = 0;

        while(fast < s.length()){
            //   // 每次遇到t中的字符，减少需要匹配的数量
            if (freq.containsKey(s.charAt(fast))){
                if (freq.get(s.charAt(fast)) > 0){

                    count--;
                }
                freq.put(s.charAt(fast), freq.get(s.charAt(fast)) - 1);

            }


            fast++;

            while(count == 0){
                if (fast - slow <= minLength){
                    minLength = fast - slow;
                    startInd = slow;
                }

                if (!freq.containsKey(s.charAt(slow))){
                    slow++;
                }else{
                    if (freq.get(s.charAt(slow)) == 0){
                        count++;
                    }
                    freq.put(s.charAt(slow), freq.get(s.charAt(slow)) + 1);

                    slow++;
                }

// 为什么要增加 count？因为当频率为 0 时，表示当前窗口已经完全包含了 t 中的所有该字符。如果我们右移 slow 指针，将这个字符移出窗口，意味着我们不再满足窗口内的完整性，所以我们需要增加 count，表示还需要一个这样的字符来恢复完整性
            }

        }

        if (minLength == Integer.MAX_VALUE){
            return "";
        } else {
            return s.substring(startInd, startInd + minLength);
        }
    }
}

// TC: O(n)
// SC: O(n)

/*
        s = "ADOBECODEBANC", t = "ABC"  Map<Character, Integer>  freq   
             s
              f 


        count 1


        A : 1
        B : 1
        C : 1 


 */