76. Minimum Window Substring

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

solution

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        t_counter = collections.Counter(t)
        s_counter = collections.defaultdict(int)

        l = 0
        valid_length = 0  # 记录窗口内和target对比的有效长度
        res = float('inf')
        res_start = -1

        for r, char in enumerate(s):
            s_counter[char] += 1
            if s_counter[char] <= t_counter[char]:
                valid_length += 1

            while valid_length == len(t):
                if r - l + 1 < res:
                    res = r - l + 1
                    res_start = l

                if s_counter[s[l]] <= t_counter[s[l]]:
                    valid_length -= 1

                s_counter[s[l]] -= 1
                l += 1

        return "" if res_start < 0 else s[res_start: res_start + res]

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

# https://zhuanlan.zhihu.com/p/143087981

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not s or not t or len(s)<len(t): # 排除特殊情况
            return ''

        s_count = collections.Counter()
        t_count = collections.Counter(t)
        l = 0
        res = ""
        for r in range(len(s)):
            s_count[s[r]] += 1

            while s_count & t_count == t_count:
                if r - l + 1 < len(res) or res == "":
                    res = s[l: r+1]
                s_count[s[l]] -= 1
                l += 1
        return res

follow up

统一思路：用哈希/数值计数器记录"still need"，双指针/滑动窗口用O(n)复杂度求解子串问题

3. Longest Substring Without Repeating Characters

30. Substring with Concatenation of All Words

class Solution(object):
    def findSubstring(self, s, words):
        if not s or not words:
            return []

        word_dict = {}
        for word in words:
            word_dict[word] = word_dict.get(word, 0) + 1

        word_len = len(words[0])
        s_len = len(s)
        max_start_pos = s_len - word_len * len(words)
        res = []

        for index in range(word_len):
            left = index
            right = index
            now_word_dict = {}
            word_cnt = 0
            while left <= max_start_pos and right + word_len <= s_len:
                now_word = s[right : right + word_len]
                right += word_len
                if now_word not in word_dict:
                    now_word_dict = {}
                    left = right
                    word_cnt = 0
                else:
                    word_cnt += 1
                    now_word_dict[now_word] = now_word_dict.get(now_word, 0) + 1
                    while now_word_dict[now_word] > word_dict[now_word]:
                        left_word = s[left : left + word_len]
                        now_word_dict[left_word] -= 1
                        left += word_len
                        word_cnt -= 1

                    if word_cnt == len(words):
                        res.append(left)
        return res

438. Find All Anagrams in a String

# https://leetcode.com/problems/find-all-anagrams-in-a-string/solutions/92007/sliding-window-algorithm-template-to-solve-all-the-leetcode-substring-search-problem/

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        if len(s) < len(p):
            return []

        p_count = {}
        for char in p:
            p_count[char] = p_count.get(char, 0) + 1

        count = {}
        for char in s[:len(p)]:
            count[char] = count.get(char, 0) + 1

        res = []
        if count == p_count:
            res.append(0)
        for index in range(len(p), len(s)):
            r = s[index]
            l = s[index - len(p)]
            count[r] = count.get(r, 0) + 1
            count[l] -= 1

            if count[l] == 0:
                del count[l]

            if count == p_count:
                res.append(index - len(p) + 1)
        return res

567. Permutation in String

class Solution(object):
    def checkInclusion(self, s1, s2):
        if len(s1) > len(s2):
            return False

        count_dict = {}
        for char in s1:
            count_dict[char] = count_dict.get(char, 0) + 1

        now_dict = {}
        for index in range(len(s1)):
            now_dict[s2[index]] = now_dict.get(s2[index], 0) + 1
        if count_dict == now_dict:
            return True

        for index in range(len(s1), len(s2)):
            remove = s2[index - len(s1)]
            now_dict[remove] -= 1
            now_dict[s2[index]] = now_dict.get(s2[index], 0) + 1
            if now_dict[remove] == 0:
                now_dict.pop(remove)

            if now_dict == count_dict:
                return True

        return False

*340. Longest Substring with At Most K Distinct Characters

992. Subarrays with K Different Integers

# 转化为 subarraysWithAtMostKDistinct(k) - subarraysWithAtMostKDistinct(k - 1)

*159. Longest Substring with At Most Two Distinct Characters

# https://walkccc.me/LeetCode/problems/0159