【Day 46 】2024-09-29 - 76. 最小覆盖子串

[azl397985856]

76. 最小覆盖子串

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/minimum-window-substring

前置知识

• Sliding Window
• 哈希表

  题目描述

  
  给你一个字符串 S、一个字符串 T 。请你设计一种算法，可以在 O(n) 的时间复杂度内，从字符串 S 里面找出：包含 T 所有字符的最小子串。

示例：

输入：S = "ADOBECODEBANC", T = "ABC" 输出："BANC"

提示：

如果 S 中不存这样的子串，则返回空字符串 ""。 如果 S 中存在这样的子串，我们保证它是唯一的答案。

[Fightforcoding]

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if len(t) > len(s) or not t or not s:
            return ""
        counter_t = Counter(t)
        required = len(counter_t)
        n = len(s)
        l, r = 0, 0
        win_counts = defaultdict(int)
        win_count = 0
        ans = float("inf"), None, None
        while r < n:
            c = s[r]
            win_counts[c] += 1

            if c in counter_t and win_counts[c] == counter_t[c]:
                win_count += 1

            while l <= r and win_count == required:
                c = s[l]

                if r - l + 1 < ans[0]:
                    ans = ( r-l+1, l, r)
                win_counts[c] -= 1
                if c in counter_t and win_counts[c] < counter_t[c]:
                    win_count -=1

                l += 1
            r += 1

        return "" if ans[0] == float("inf") else s[ans[1] : ans[2] + 1]

Time: O(N+M) N is length of s, M is length of t

Space: O(p) p is length of s substring

[qiaoeve]

思路：滑动窗口

class Solution: def minWindow(self, s: str, t: str) -> str: ans_left, ans_right = -1, len(s) cnt = defaultdict(int) for c in t: cnt[c] += 1 less = len(cnt) # 有 less 种字母的出现次数 < t 中的字母出现次数 left = 0 for right, c in enumerate(s): # 移动子串右端点 cnt[c] -= 1 # 右端点字母移入子串 if cnt[c] == 0:

原来窗口内 c 的出现次数比 t 的少，现在一样多

            less -= 1
        while less == 0:  # 涵盖：所有字母的出现次数都是 >=
            if right - left < ans_right - ans_left:  # 找到更短的子串
                ans_left, ans_right = left, right  # 记录此时的左右端点
            x = s[left]  # 左端点字母
            if cnt[x] == 0:
                # x 移出窗口之前，检查出现次数，
                # 如果窗口内 x 的出现次数和 t 一样，
                # 那么 x 移出窗口后，窗口内 x 的出现次数比 t 的少
                less += 1
            cnt[x] += 1  # 左端点字母移出子串
            left += 1
    return "" if ans_left < 0 else s[ans_left: ans_right + 1]

时间复杂度：O(m+n)