最小窗口子串无法正确滑动

Question

问题

最小窗口子串 给定两个长度分别为 m 和 n 的字符串 s 和 t，返回最小窗口 子串 s 使得 t 中的每个字符（包括重复字符）都包含在窗口中。如果不存在这样的子字符串，则返回空字符串“”。 生成的测试用例的答案是唯一的。

问题链接

逻辑

我的逻辑如下

• 为 t 创建一个字符频率字典

  t_freq

  ，您可以在其中更新并填充字符的频率
• 为 s 中的窗口创建一个字符频率字典

  s_freq

  ，并且仅创建 t 中的字母。
• 一旦到达

  t_freq == s_freq

  的阶段，您就会比较长度并尝试找到

  min_len

  和

  min_ans

• 然后您滑动搜索窗口以寻找更好的选项（更小的长度）

代码

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if s == t:
            return s
        curr_len = 0
        min_len = float("inf")

        t_freq = {char: 0 for char in set(t)}
        s_freq = {char: 0 for char in set(t)}
        for char in t:
            t_freq[char] +=1
        i=0
        j=0
        N = len(s)
        min_ans = ""
        while j < N:
            if s[j] in s_freq:
                s_freq[s[j]] +=1
            if t_freq == s_freq:
                curr_len = j-i+1
                min_len = min(min_len, curr_len)
                min_ans = s[i:j+1]
                if s[i] in s_freq:
                    s_freq[s[i]] -= 1
                i+=1
            j+=1
        return min_ans

问题

问题是我没有很好地滑动窗户。它不考虑其他选择。例如在测试用例中

s = "AOBCOBAC", t = "ABC"

它返回

"AOBC"

，公平地说，它找到了子字符串的第一个实例并计算长度。但它将来永远不会考虑

"BAC"

，因为我的猜测是我没有增加足够的时间使整个字典为0，所以它可以将

"BAC"

处理为

{C:1, B:1, A:1}

，又名我不是滑动窗口，所以它涵盖了每个部分/类型的子串。我该怎么办？

Answer 1

维护当前窗口的左右索引。对于窗口的每个可能的起始（左）索引，将右索引向前移动，直到每个字符的频率达到最低要求。不要直接比较两个频率词典，因为这与词典的大小成线性关系；相反，您可以统计到目前为止匹配的字符数量。

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        from collections import Counter
        t_count = Counter(t)
        curr_count = Counter()
        n = len(s)
        l = r = good = 0
        start = n
        size = n + 1
        for l in range(n):
            while r < n and good != len(t_count):
                curr_count[s[r]] += 1
                if curr_count[s[r]] == t_count[s[r]]: good += 1
                r += 1
            if good == len(t_count) and r - l < size:
                start = l
                size = r - l
            curr_count[s[l]] -= 1
            if curr_count[s[l]] < t_count[s[l]]: good -= 1
        return s[start:start + size]