题目

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
• 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

示例 3:

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

提示：

• ^{m == s.length}
• ^{n == t.length}
• 1 <= m, n <= 10⁵
• s 和 t 由英文字母组成

解法

滑动窗口 + 计数数组判断是否涵盖子串

因为s 和 t 由英文字母组成，可以用一个长度为58的数组来保存每个字母出现的频次（A到a为32，32+26=58）

维护一个窗口内的字母频次数组。

每次滑动窗口前判断窗口中的频次是否符合要求（涵盖子串t），

• 如果不涵盖，通过滑动右边界扩展窗口；
• 如果涵盖，通过滑动左边界缩小窗口至满足要求的最短长度，记录此时的左指针和右指针；

重复滑动窗口直至右窗口抵达边界，且得到该右窗口下满足条件的最短子串

class Solution {
    public String minWindow(String s, String t) {
        int min_length = 100001;
        int[] result_index = null;
 
        char[] chars_t = t.toCharArray();
        int[] cnt_t = new int[58]; // 32 + 26 = 58
        for (char c : chars_t) cnt_t[c - 'A']++;
        
        // 窗口中字符数量计数数组
        int[] cnt_window = new int[58];
        char[] char_s = s.toCharArray();
        int left = 0, right = 0;
        cnt_window[char_s[right] - 'A']++;
        while (right < char_s.length) {
            if (!isContains(cnt_window, cnt_t)) {
                // 窗口中不包含子串
                right++;
                if (right < char_s.length) cnt_window[char_s[right] - 'A']++;
            } else {
                if (right-left+1 < min_length) {
                    min_length = right-left+1;
                    result_index = new int[2];
                    result_index[0] = left;
                    result_index[1] = right;
                }
                cnt_window[char_s[left] - 'A']--;
                left++;
            }
        } 
        if (null == result_index) return "";
        return s.substring(result_index[0], result_index[1]+1);
    }
 
    // 判断a中是否包含b
    private boolean isContains(int[] a, int[] b) {
        for (int i = 0; i < 58; i++) {
            if (a[i] - b[i] < 0) return false;
        }
        return true;
    }
}

				

					
				
				

					
				
				

					
				
				

					
				
			

时间复杂度：O(N)

优化一

当前代码每次窗口移动时都调用 isContains 函数，逐个字符比较频次，耗时过多。
优化：可以通过维护一个计数器 matched 来减少这类比较操作，只在字符真正匹配时调整。

在右边界移动，纳入新的元素入窗口后，只要比较 cnt_window[right] 和 cnt_t[right]

• 如果cnt_window[right]<=cnt_t[right]，说明新加入的字符一定在t中，且还没有比t中这个字符的数量多。（如果t中没有这个字符，就会cnt_window[right]》cnt_t[right]）

class Solution {
    public String minWindow(String s, String t) {
        // 滑动窗口，不符合要求时扩张窗口，符合要求缩减
        // 用cnt记录t中的不同字母数，窗口中符合要求的字母数等于这个就是匹配
        int left = 0, right = 0, cnt_char_t = 0, cnt_char_s = 0;
        int[] cnt_t = new int[58], cnt_s = new int[58];
        char[] chars_t = t.toCharArray(), chars_s = s.toCharArray();
        int length_result = Integer.MAX_VALUE, result_left = 0;
 
        for (char c : chars_t) {
            if (cnt_t[c - 'A'] == 0) cnt_char_t++;
            cnt_t[c - 'A']++;
        }
            
        // 开始窗口滑动
        while (right < s.length()) {
            cnt_s[chars_s[right] - 'A']++;
            if (cnt_t[chars_s[right] - 'A'] == cnt_s[chars_s[right] - 'A']) {
                cnt_char_s++;
            } 
            while (cnt_char_t == cnt_char_s) {
                if (length_result > right - left + 1) {
                    length_result = right - left + 1;
                    result_left = left;
                }
                // 符合要求就缩减左边界，直到不符合要求
                cnt_s[chars_s[left] - 'A']--;
                if (cnt_t[chars_s[left] - 'A'] > cnt_s[chars_s[left] - 'A']) cnt_char_s--;
                left++;
            }
            // 到这里肯定不符合要求，继续扩张
            right++;
        }
        if (length_result == Integer.MAX_VALUE) return "";
        // 返回结果
        return new String(chars_s, result_left, length_result);
    }
}

				

					
				
				

					
				
				

					
				
				

					
				
			

小结

再次体会到活动窗口的精髓：仅仅维护出窗口和入窗口的元素。

一个String的构造函数： new String(char[] value, int offset, int count)

参数：

• value: 原始的字符数组。
• offset: 起始索引，即 index_l。
• count: 要转换的字符个数，即 index_r – index_l + 1。