LeetCode 567 · Sliding Window

Permutation in String, explained with a picture

A letter stencil sliding along a strip.

MediumSliding Window
▶ Watch it step by step

The problem

Given two strings s1 and s2, return true if s2 contains some rearrangement of s1 as a block of consecutive letters.

Input:  s1 = "ab", s2 = "eidbaooo"
Output: true   ("ba" appears in s2)

Picture it

Picture a stencil exactly as wide as s1, sliding along a strip of letters (s2). At each spot we compare the letter counts under the stencil with the counts s1 needs. When they match exactly, the letters under the stencil are a rearrangement of s1. Sliding one step only adds one letter on the right and removes one on the left, so updating the counts is quick.

How to recognise it

  • You are looking for a block of consecutive characters with a fixed length: the length of s1.
  • "Some rearrangement of s1" means the block must have the same letter counts as s1. Order does not matter.
  • A fixed-length window that moves one step at a time changes by exactly one letter in and one letter out, so its counts can be updated in O(1).
  • Both strings have up to 10^4 lowercase letters.

Start with brute force

The literal approach, trying every permutation of s1, is hopeless: a 10-letter s1 already has 3,628,800 of them. A more sensible brute force checks every block of s2 with the right length and compares its letter counts with s1's.

from collections import Counter

def check_inclusion_brute(s1, s2):
    m = len(s1)
    need = Counter(s1)
    for i in range(len(s2) - m + 1):
        if Counter(s2[i:i + m]) == need:
            return True
    return False

Each block is counted from scratch, so time is O((n − m + 1) · m), where n = len(s2). The worst case is m about n/2: with n = 10^4 that is about 2.5 × 10^7 character counts, slow in Python. Space is O(1), at most 26 letters per count.

From brute force to the idea

  1. Find the waste. Neighbouring blocks share m − 1 letters, yet each is counted again from nothing.
  2. Count the first window once. win = Counter(s2[:m]) holds the counts of the first block.
  3. Slide by one. For the block ending at i, add s2[i] and remove s2[i - m]. That is two O(1) updates instead of m.
  4. Compare counts. If win == need at any point, a rearrangement of s1 sits there. Comparing two Counters of lowercase letters looks at no more than 26 keys.
  5. Check the last window too. The loop compares before each slide, so the final window is compared by the return win == need after the loop.

This is the key idea: a fixed-size window whose letter counts are updated with one letter in and one letter out.

The key idea

Fixed-size window with letter counts. Slide by adding one letter and removing one; compare counts. O(n).

Python solution

def check_inclusion(s1, s2):
    m = len(s1)
    need, win = Counter(s1), Counter(s2[:m])
    for i in range(m, len(s2)):
        if win == need:
            return True
        win[s2[i]] += 1             # letter enters
        win[s2[i - m]] -= 1         # letter leaves
    return win == need

LeetCode adds the imports for you. To run this on your own machine, put this at the top: from collections import Counter

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO((n − m + 1) · m): every block is counted from scratchO(1): at most 26 counts
Sliding counts (shown code)O(m + 26 · n): two updates and one comparison of at most 26 keys per stepO(1): two Counters of at most 26 letters

Edge cases

  • s1 longer than s2 ("abc", "ab"): returns False. The first window is all of s2, the loop never runs, and the counts differ.
  • Match at the very end ("ab", "xxab"): returns True, found by the final comparison.
  • Match at the start ("ab", "ab"): returns True.
  • Zero counts: removed letters stay in win with count 0. Since Python 3.10, Counter equality treats a missing letter and a count of 0 as equal. On Python 3.9 or older, win == need compares them like plain dictionaries, so ("ab", "cab") would wrongly return False; deleting keys that reach 0 avoids this.
  • Missing import: the code needs from collections import Counter; without it the call raises NameError.

Common mistakes

  • Returning False after the loop instead of win == need, which misses a match in the last window: ("ab", "xxab") then returns False.
  • Removing s2[i - m + 1] instead of s2[i - m]. That letter is still inside the window, so the counts stop matching the block they describe.
  • Comparing sets of letters instead of counts, so "aab" matches "abb".
  • Rebuilding Counter(s2[i - m + 1:i + 1]) on each step, which brings back the O(n · m) cost.
Your turn: every starting position

Return all starting positions in s where a rearrangement of p begins. For s = "cbaebabacd" and p = "abc" the answer is [0, 6]; for "abab" and "ab" it is [0, 1, 2]. Describe your approach, then write it if you like.

Compare with our answer

Same window, but instead of returning at the first match, record its start and keep sliding. Loop one step further so the last window is checked inside the loop, and only slide while there is a letter left to add.

from collections import Counter

def find_anagrams(s, p):
    m, out = len(p), []
    need, win = Counter(p), Counter(s[:m])
    for i in range(m, len(s) + 1):
        if win == need:
            out.append(i - m)          # window is s[i - m:i]
        if i < len(s):
            win[s[i]] += 1
            win[s[i - m]] -= 1
    return out

Time O(m + 26 · n), space O(1) besides the answer. Overlapping matches are all found.

A strong answer mentions: recording the start i - m, not stopping at the first match, and checking the final window.

Check what stuck

1. You must count the 10-letter blocks of a DNA string that have exactly the same letter counts as a given 10-letter pattern. Which approach fits best?

2. Why is each step of the shown code cheap even though it compares two Counters?

3. A learner replaces the final return win == need with return False. Which call now returns the wrong answer?

Score 60% or more and the lesson is marked complete.