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

Question

问题

最小窗口子串 给定两个字符串 s 和 t，长度分别为 m 和 n，返回 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 {
    public String minWindow(String s, String t) {
        int n = s.length();
        int m = t.length();
        HashMap<Character, Integer> map = new HashMap<>();
        int count = 0;
        int start = -1;
        int min = Integer.MAX_VALUE;
        int l = 0;
        int r = 0;
        for (int i = 0; i < m; i++)
            map.put(t.charAt(i), map.getOrDefault(t.charAt(i), 0) + 1);
        while (r < n) {
            if (map.getOrDefault(s.charAt(r), 0) > 0)
                count++;
            map.put(s.charAt(r), map.getOrDefault(s.charAt(r), 0) - 1);
            while (count == m) {
                if (r - l + 1 < min) {
                    min = r - l + 1;
                    start = l;
                }
                map.put(s.charAt(l), map.get(s.charAt(l)) + 1);
                if (map.get(s.charAt(l)) > 0)
                    count--;
                l++;
            }

            r++;
        }
        if (start == -1)
            return "";
        return s.substring(start, start + min);
    }
}

当然可以！请把你想要翻译的内容发给我，我会帮你用简单易懂的语言解释清楚。

Answer 2

保持当前窗口的左边和右边的索引。对于窗口的每一个可能的起始（左边）索引，向前移动右边的索引，直到每个字符的出现频率达到了最低要求。不要直接比较两个频率的字典，因为那样会随着字典的大小线性增长；相反，你可以记录到目前为止有多少个字符是匹配的。

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]