最小覆盖子串

2025/10/16

思路：只需统计词频，中间无关的字符可以用用个数替代。然后就不会做了

评价：我好像感觉到了要用滑动窗口，但是没有想下去

推荐思路：滑动窗口

2025/10/19

思路：看到例子能想到是滑动窗口。

def minWindow(s: str, t: str) -> str:
    if s == []:
        return ""
    
    frequency_t = {}
    for char in t:
        if char not in frequency_t.keys():
            frequency_t[char] = 1
        frequency_t[char] += 1

    min_interval = float('inf')
    min_left, min_right = 0, 0

    frequency_current = {char: 0 for char in frequency_t.keys()}
    left, right = 0, 0
    frequency_t[s[0]] = 1
    while !is_frequency_same(frequency_current, frequency_t):
        right = right + 1
        if char in frequency_t.keys():
            frequency_t[s[right]] += 1
        min_interval = right - left
        min_left, min_right = left, right
    
    while right < len(s):
        while s[left] not in frequency_current: 
            left += 1
        if s[left] in frequency_t.keys():
            frequency_current[s[left]] -= 1
            if right - left < min_interval:
                min_interval = right - left
                min_left, min_right = left, right
            if frequency_current < frequency_t:
                deleted_char = s[left]
                while s[left] not in frequency_current: 
                    left += 1
                while s[right] != deleted_char and right < len(s):
                    if char in frequency_t.keys():
                        frequency_t[s[right]] += 1
                        if right - left < min_interval:
                            min_interval = right - left
                            min_left, min_right = left, right
                    right += 1
            
        return s[min_left:min_right]