滑动窗口 | 满足条件的最短的子串

字数统计: 1.3k字   |   阅读时长: 5分

摘要: 滑动窗口解决字符计数满足条件的最短子串的问题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

各位好，前面两篇文章 滑动窗口 | 满足条件的子串数目、滑动窗口字符计数的优化：增加维护聚合信息应对高频查询 中，我们介绍了在一个字符串中统计字符计数满足一定条件的子串数目的问题，其核心是滑动窗口，并用字符计数（本质是哈希表）维护所需的信息。

本文我们看一下相同场景下寻找字符计数满足一定条件的最短的子串的问题，问题描述一样，只是统计个数变成了找最短的。

众所周知 leetcode 每周有周赛、每两周有双周赛，每周还有一两道原创新题，题目增长还是非常稳定的，现在已经 3500 左右了。而今天的题是非常早期的题，第 76 题，基本上刷过 leetcode 的基本都做过这题吧，大家已经研究透了，像接雨水一样经典，本文可以当成一个经典回顾。

题目

• 76. 最小覆盖子串

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

注意：

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

提示：

1
2
3
4

m == s.length
n == t.length
1 <= m, n <= 1e5
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 的子串中，
因此没有符合条件的子字符串，返回空字符串。

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

题解

算法: 双指针

t 的字符计数记为 target。在 s 中推进滑动窗口，推进 right 指针加入窗口的新字符，将其在 target 中 -1、推进 left 指针移出窗口的字符，将其在 target 中 +1。

这样的话，t 中没有的字符，target 中的计数始终是不大于 0 的，它与窗口是否合法无关。而对于 t 中有的字符 c，在 target 中有以下状态：

• target[c] > 0：窗口内的 c 字符尚不满足要求；
• target[c] = 0：窗口内恰含有所需的字符 c 的个数；
• target[c] < 0：窗口内有多余的 c 字符。

窗口是否合法仅取决于窗口内尚未满足条件的字符个数 x，x 初始时为 t 中的字符种类数。当 x = 0 时，窗口合法。因此推进滑动窗口时，除了 target 这一字符计数的信息之外，再维护一个尚未满足的字符个数 x，这是一个聚合信息。

下面考虑推进滑动窗口的双指针的过程：

当窗口不满足条件时，向右推进 right 指针，加入字符 c，更新 target[c] -= 1，这一步若使得 target[c] 从 1 变为 0，意味着新加入的字符从不满足条件变为满足条件，此时更新 x -= 1，若这步更新又使得 x 变为 0，意味着窗口从不合法变为合法，此时若 right 继续向右移动，窗口当然还是合法的，但由于我们要找的是最短合法子串，因此 right 就不要继续推进了，此时的 right 表示的就是当前左端点为 left 的情况下，满足条件的最小窗口，用 right - left + 1 更新答案即可。（在统计合法子串个数的问题中，这里直接把 n - right + 1 作为以 left 为起点的合法窗口的数目更新答案即可，同样不用继续向右推进 right）。

然后将左端点 left 推进 1，移出窗口的字符为 c，更新 target[c] += 1，若这一步使得 target[c] 变为 1，则字符 c 从合法变不合法，更新 x += 1，继续以上推进 right 的过程，直至 s 串耗尽即可。

代码 (Python)

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

from collections import Counter

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        n1 = len(s)
        INF = n1 + 1
        target = Counter(t)
        x = len(target)
        l = 0
        r = -1
        min_len = n1 + 1
        result = ""
        while l < n1 and r < n1:
            while x > 0:
                r += 1
                if r >= n1:
                    break
                target[s[r]] -= 1
                
                if target[s[r]] == 0:
                    x -= 1

            if r < n1:
                if r - l + 1 < min_len:
                    min_len = r - l + 1
                    result = s[l:r+1]
            target[s[l]] += 1
            
            if target[s[l]] > 0:
                x += 1
            l += 1
        return result