Skip to content

定长滑动窗口进阶 Fixed Sliding Window Size Advanced

Table of Contents

1461. Check If a String Contains All Binary Codes of Size K

  • LeetCode | 力扣

  • Tags: Hash Table, String, Bit Manipulation, Rolling Hash, Hash Function

2134. Minimum Swaps to Group All 1's Together II

1297. Maximum Number of Occurrences of a Substring

2653. Sliding Subarray Beauty

3439. Reschedule Meetings for Maximum Free Time I

1888. Minimum Number of Flips to Make the Binary String Alternating

  • LeetCode | 力扣

  • Tags: String, Dynamic Programming, Greedy, Sliding Window

567. Permutation in String

  • LeetCode | 力扣

  • Tags: Hash Table, Two Pointers, String, Sliding Window

def checkInclusion(s1: str, s2: str) -> bool:
    if len(s1) > len(s2):
        return False

    count1 = [0] * 26
    count2 = [0] * 26

    for i in range(len(s1)):
        count1[ord(s1[i]) - ord("a")] += 1
        count2[ord(s2[i]) - ord("a")] += 1

    matches = 0
    for i in range(26):
        if count1[i] == count2[i]:
            matches += 1

    l = 0
    for r in range(len(s1), len(s2)):
        if matches == 26:
            return True

        index = ord(s2[r]) - ord("a")
        count2[index] += 1
        if count1[index] == count2[index]:
            matches += 1
        elif count1[index] + 1 == count2[index]:
            matches -= 1

        index = ord(s2[l]) - ord("a")
        count2[index] -= 1
        if count1[index] == count2[index]:
            matches += 1
        elif count1[index] - 1 == count2[index]:
            matches -= 1

        l += 1

    return matches == 26


s1 = "ab"
s2 = "eidba"
print(checkInclusion(s1, s2))  # True

438. Find All Anagrams in a String

from typing import List


class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        """Fixed Sliding Window: O(n + m) time, O(1) space.
        Track 26 lowercase counts for the current window of length len(p).
        """
        if len(p) > len(s):
            return []

        target = [0] * 26
        window = [0] * 26
        for i, ch in enumerate(p):
            target[ord(ch) - ord("a")] += 1
            window[ord(s[i]) - ord("a")] += 1

        res = []
        if window == target:
            res.append(0)

        left = 0
        for right in range(len(p), len(s)):
            window[ord(s[right]) - ord("a")] += 1
            window[ord(s[left]) - ord("a")] -= 1
            left += 1
            if window == target:
                res.append(left)

        return res


def test_find_anagrams():
    s = Solution()
    assert s.findAnagrams("cbaebabacd", "abc") == [0, 6]
    assert s.findAnagrams("abab", "ab") == [0, 1, 2]
    assert s.findAnagrams("af", "be") == []
    assert s.findAnagrams("baa", "aa") == [1]
    assert s.findAnagrams("", "a") == []

30. Substring with Concatenation of All Words

2156. Find Substring With Given Hash Value

  • LeetCode | 力扣

  • Tags: String, Sliding Window, Rolling Hash, Hash Function

2953. Count Complete Substrings

1016. Binary String With Substrings Representing 1 To N

683. K Empty Slots 👑

  • LeetCode | 力扣

  • Tags: Array, Binary Indexed Tree, Segment Tree, Queue, Sliding Window, Heap Priority Queue, Ordered Set, Monotonic Queue

2067. Number of Equal Count Substrings 👑

2524. Maximum Frequency Score of a Subarray 👑

  • LeetCode | 力扣

  • Tags: Array, Hash Table, Math, Stack, Sliding Window