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

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.

Constraints:

m == s.length
n == t.length
1 <= m, n <= 10^5
s and t consist of uppercase and lowercase English letters.

解法1

滑动窗口.

class Solution {
    public String minWindow(String s, String t) {
        // 用map来保存字符串t中含有的字符, 以及数量
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        for(char c : t.toCharArray())
            map.put(c, map.getOrDefault(c, 0) + 1);
        // t中含有的字符的个数
        int charNums = map.size();

        // 用caMap来保存滑动窗口中含有的字符,以及数量
        Map<Character, Integer> caMap = new HashMap<Character, Integer>();
        // 最终结果的窗口长度, 左边界和右边界
        int res = -1 , rl = 0, rr = 0;
        // 滑动窗口的左边界和右边界
        int left = 0, right = 0;
        int len = s.length();
        // 滑动窗口中含有的满足条件的字符的个数(条件为, 该字符的数量和t中该字符的数量一致)
        int caCharNums = 0;
        
        
        while(right < len){
            // 右边界
            char c = s.charAt(right);
            // 如果map中包含c
            if(map.containsKey(c)){
                
                caMap.put(c, caMap.getOrDefault(c, 0) + 1);
                // 如果c在map和caMap中的数量一致(在当前窗口中,c字符的数量一致)
                // 那么滑动窗口中一直的字符的个数加1
                if(map.get(c).intValue() == caMap.get(c).intValue())
                    caCharNums++;
                
                // 在滑动窗口包含了t中的所有字符时, 尝试移动左边界来缩短窗口长度
                while(caCharNums == charNums){
                    char cl = s.charAt(left);
                    // 如果左边界的字符在map中有, 那么开始计算
                    // 其实当前滑动窗口的长度在无效字符(左边界在map中不存在)时也可以计算
                    //     但是只在碰到有效字符时才计算可以减少计算次数.
                    if(map.containsKey(cl)){
                        // 如果这是第一次得到满足条件的滑动窗口,或者这一次比上一次的窗口长度小
                        // 更新最终结果
                         if(res == -1 || right - left + 1 < res){
                            res = right - left + 1;
                            rl = left;
                            rr = right;
                        }

                        // 当前左边界对应的字符的数量减1
                        caMap.put(cl, caMap.get(cl)-1);
                        // 如果字符数量小于map中该字符的数量,
                        if(map.get(cl).intValue() > caMap.get(cl).intValue())
                            caCharNums--;
                    }
                    // 窗口左边界向右移动
                    left++;
                }
            }
            
            // 窗口右边界向右移动
            right++;         
        }
        
        return res == -1 ? "" : s.substring(rl, rr + 1);
    } 
           
}

0076. Minimum Window Substring - kumaeki/LeetCode GitHub Wiki

解法1