最小覆盖子串

难度:

标签:

题目描述

给你一个字符串 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 由英文字母组成

进阶：你能设计一个在 o(m+n) 时间内解决此问题的算法吗？

代码结果

运行时间: 188 ms, 内存: 15.3 MB

/*
 * Problem Statement: Same as above, solve using Java Stream.
 *
 * Approach:
 * This problem doesn't naturally lend itself to Java Stream due to its mutable state requirements (window management).
 * However, we can still implement the logic in a Stream-like fashion by using helper methods and a more functional style.
 */
 
import java.util.HashMap;
import java.util.Map;
import java.util.stream.IntStream;
 
public class MinWindowSubstringStream {
    public String minWindow(String s, String t) {
        if (s == null || t == null || s.length() < t.length()) return "";
        Map<Character, Integer> mapT = new HashMap<>();
        t.chars().forEach(c -> mapT.put((char) c, mapT.getOrDefault((char) c, 0) + 1));
        int required = mapT.size();
        Map<Character, Integer> windowCounts = new HashMap<>();
        int[] ans = {Integer.MAX_VALUE, 0, 0}; // length, left, right
        int[] formedAndLeft = {0, 0}; // formed, left
        IntStream.range(0, s.length()).forEach(right -> {
            char c = s.charAt(right);
            windowCounts.put(c, windowCounts.getOrDefault(c, 0) + 1);
            if (mapT.containsKey(c) && windowCounts.get(c).intValue() == mapT.get(c).intValue()) {
                formedAndLeft[0]++;
            }
            while (formedAndLeft[1] <= right && formedAndLeft[0] == required) {
                c = s.charAt(formedAndLeft[1]);
                if (right - formedAndLeft[1] + 1 < ans[0]) {
                    ans[0] = right - formedAndLeft[1] + 1;
                    ans[1] = formedAndLeft[1];
                    ans[2] = right;
                }
                windowCounts.put(c, windowCounts.get(c) - 1);
                if (mapT.containsKey(c) && windowCounts.get(c).intValue() < mapT.get(c).intValue()) {
                    formedAndLeft[0]--;
                }
                formedAndLeft[1]++;
            }
        });
        return ans[0] == Integer.MAX_VALUE ? "" : s.substring(ans[1], ans[2] + 1);
    }
}

解释

方法:

题解采用了滑动窗口的策略来寻找包含字符串t所有字符的最小子串。首先，使用字典need记录字符串t中各字符的数量。另外使用窗口字典window记录当前窗口中各字符的数量。通过移动右指针right扩展窗口，当窗口中包含t的所有字符后（即窗口中的字符数量满足t的需求），尝试通过移动左指针left缩小窗口，同时更新记录最小窗口的start和length变量。窗口有效时进行缩小操作，不再有效时继续扩展右指针。最后，根据记录的start和length输出最小覆盖子串。

时间复杂度:

O(m + n)

空间复杂度:

O(1)

代码细节讲解

🦆

在滑动窗口算法中，如何准确判断何时窗口中包含了字符串t的所有字符？

▷

在滑动窗口算法中，通过使用两个字典`need`和`window`来分别记录字符串t中每个字符需要的数量和当前窗口中各字符的实际数量。同时，使用一个计数器`valid`来记录当前窗口中满足t中字符需求的字符类型数。每当一个字符在窗口中的数量达到其在t中的需求时，`valid`计数器加1。当`valid`的值等于`need`字典中键的数量（即t中不同字符的数量）时，说明窗口已经包含了t的所有字符。

🦆

为什么在窗口包含所有必需字符后立即尝试缩小窗口，这种策略如何确保找到的子串长度最小？

▷

当窗口首次包含了t的所有字符后，此时的窗口是一个可能的解，但可能不是最小解。接下来尝试通过移动左指针`left`来缩小窗口的大小。这是为了探索是否存在更小的窗口同样包含t的所有字符。每次移动左指针时，都会检查缩小后的窗口是否仍满足条件，这通过减少左指针字符的数量并更新`valid`值来实现。只有当窗口仍然有效时（即包含t的所有字符），我们才更新记录最小子串的起始位置和长度。这种策略通过不断尝试减小窗口的长度，直到不再满足条件，从而确保找到的子串是最小的。

🦆

在移动左指针缩小窗口时，如何处理窗口中字符数量变化对need条件的影响？

▷

在移动左指针`left`减小窗口大小时，会减少离开窗口字符的数量。对于每一个离开窗口的字符`d`，窗口字典`window`中该字符的数量减1。如果减少后的数量小于在`need`字典中记录的需求数量，并且该字符是t中的字符，则`valid`计数器减1。这意味着窗口不再满足包含t的所有字符的条件。这种处理方式确保了每次缩小窗口时，我们都会准确地评估窗口的有效性（是否包含t的所有字符）。

🦆

如果字符串s中包含t中未出现的字符，这些字符在算法中是如何处理的？

▷

如果字符串s中包含t中未出现的字符，这些字符在`need`字典中的计数为0，因此在维护`window`字典时，这些字符虽然会被记录其数量，但不会影响`valid`计数器的值。窗口的扩展和缩小仅考虑那些在`need`字典中存在的字符。这意味着，虽然这些未出现在t中的字符会被计入窗口，但它们不影响窗口是否满足覆盖子串的条件。这样的处理简化了算法的逻辑，使其专注于t中的字符。

相关问题

串联所有单词的子串

给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。

s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。

例如，如果 words = ["ab","cd","ef"]，那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"，和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。

返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。

示例 1：

输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]
解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。
子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。
子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。

示例 2：

输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出：[]
解释：因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。

示例 3：

输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
输出：[6,9,12]
解释：因为 words.length == 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。
子串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。
子串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。
子串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。

提示：

1 <= s.length <= 10⁴
1 <= words.length <= 5000
1 <= words[i].length <= 30
words[i] 和 s 由小写英文字母组成

长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [nums_l, nums_l+1, ..., nums_r-1, nums_r] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

输入：target = 4, nums = [1,4,4]
输出：1

示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

提示：

1 <= target <= 10⁹
1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵

进阶：

如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

示例 2：

输入：nums = [1], k = 1
输出：[1]

提示：

1 <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴
1 <= k <= nums.length

字符串的排列

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。

换句话说，s1 的排列之一是 s2 的子串。

示例 1：

输入：s1 = "ab" s2 = "eidbaooo"
输出：true
解释：s2 包含 s1 的排列之一 ("ba").

示例 2：

输入：s1= "ab" s2 = "eidboaoo"
输出：false

提示：

1 <= s1.length, s2.length <= 10⁴
s1 和 s2 仅包含小写字母

最小窗口子序列

颜色分类组合