76 Minimum Window Substring

Leetcode

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.

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' 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.

---

使用滑动窗口求解。使用一个 boolean 数组来表示一个字符是否是 t 中的字符，使用一个 int 数组来表示窗口中每个字符还差的个数。向右移动窗口，直到所有 t 中的字符的数量在窗口中足够，然后尝试移动窗口的左边缩短窗口，记录窗口长度，不断重复。返回最小的窗口长度。

public String minWindow(String s, String t) {
    boolean[] need=new boolean[128];
    int[] count=new int[128];
    int num=0;
    for(int i=0;i<t.length();++i){
        char c=t.charAt(i);
        if(!need[c]){
            need[c]=true;
            num++;
        }    
        count[c]++;
    }
    
    int left=0, right=0;
    int len=Integer.MAX_VALUE, start=0;
    int valid=0;
    while(right<s.length()){
        char c=s.charAt(right);
        right++;
        
        if(need[c]){
            if(count[c]==1) valid++;
            count[c]--;
        }
        
        while(valid==num){
            if(len>right-left){
                len=right-left;
                start=left;
            }
            
            char d=s.charAt(left);
            if(need[d]){
                if(count[d]==0) {
                    valid--;
                }
                count[d]++;
            }
            left++;
        }
    }
    if(len==Integer.MAX_VALUE) return "";
    return s.substring(start,start+len);
}