Leetcode_hot100_76.最小覆盖子串

题目要求

  • 给定两个字符串 s 和 t，长度分别是 m 和 n，返回 s 中的 最短窗口 子串，使得该子串包含 t 中的每一个字符（包括重复字符）。如果没有这样的子串，返回空字符串 “”。

  • 测试用例保证答案唯一。

示例 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 的子串中，
因此没有符合条件的子字符串，返回空字符串。

滑动窗口

枚举s子串的右端点right，如果子串涵盖t，就不断移动左端点直至不涵盖t，移动期间判断是否是最小子串。

如何判断s子串是否涵盖t？
cntT记录t中每个字符出现的次数，cntS记录s子串中每个字符出现的次数，如果对于t中的每个字符c，都有cntS[c] >= cntT[c]，则s子串涵盖t。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
    public String minWindow(String s, String t) {
        int[] cntS = new int[128];
        int[] cntT = new int[128];
        for (char c : t.toCharArray()) {
            cntT[c]++;
        }

        int left = 0;
        char[] arrS = s.toCharArray();
        int n = arrS.length;
        int ansLeft = -1, ansRight = n;

        for (int right = 0; right < n; right++) {
            // s的右端点计入子串
            cntS[arrS[right]]++;
            // 判断当前子串是否涵盖t
            while (isCover(cntS, cntT)) {
                // 更新答案
                if (right - left < ansRight - ansLeft) {
                    ansLeft = left;
                    ansRight = right;
                }
                // s的左端点移出子串
                cntS[arrS[left]]--;
                left++;
            }
        }

        return ansLeft == -1 ? "" : s.substring(ansLeft, ansRight + 1);
    }

    public boolean isCover(int[] cntS, int[] cntT) {
        for (int i = 0; i < 128; i++) {
            if (cntS[i] < cntT[i]) {
                return false;
            }
        }
        return true;
    }
}
  • 时间复杂度：O(|Σ|m+n)，其中 m 和 n 分别是字符串 s 和 t 的长度，|Σ|是字符集合的大小。
  • 空间复杂度：O(|Σ|)，其中 |Σ| 是字符集合的大小。