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 ass1. 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
- Find the waste. Neighbouring blocks share m − 1 letters, yet each is counted again from nothing.
- Count the first window once.
win = Counter(s2[:m])holds the counts of the first block. - Slide by one. For the block ending at i, add
s2[i]and removes2[i - m]. That is two O(1) updates instead of m. - Compare counts. If
win == needat any point, a rearrangement ofs1sits there. Comparing two Counters of lowercase letters looks at no more than 26 keys. - Check the last window too. The loop compares before each slide, so the final window is compared by the
return win == needafter 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 == needLeetCode 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
| Approach | Time | Space |
|---|---|---|
| Brute force | O((n − m + 1) · m): every block is counted from scratch | O(1): at most 26 counts |
| Sliding counts (shown code) | O(m + 26 · n): two updates and one comparison of at most 26 keys per step | O(1): two Counters of at most 26 letters |
Edge cases
s1longer thans2("abc","ab"): returnsFalse. The first window is all ofs2, the loop never runs, and the counts differ.- Match at the very end (
"ab","xxab"): returnsTrue, found by the final comparison. - Match at the start (
"ab","ab"): returnsTrue. - Zero counts: removed letters stay in
winwith 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 == needcompares them like plain dictionaries, so("ab", "cab")would wrongly returnFalse; deleting keys that reach 0 avoids this. - Missing import: the code needs
from collections import Counter; without it the call raisesNameError.
Common mistakes
- Returning
Falseafter the loop instead ofwin == need, which misses a match in the last window:("ab", "xxab")then returnsFalse. - Removing
s2[i - m + 1]instead ofs2[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.
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.
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?
The block length is fixed, so the window simply slides with two O(1) updates. Sorting every block costs O(m log m) each, and a pattern of 10 letters can have up to 3,628,800 permutations.
2. Why is each step of the shown code cheap even though it compares two Counters?
Comparing Counters checks every key, but there are at most 26 of them, so it is O(26) per step. Counters are not compared by their totals, and the window is updated, not rebuilt.
3. A learner replaces the final return win == need with return False. Which call now returns the wrong answer?
In "xxab" the only match is the last window, which the loop never compares. The other matches are found inside the loop, and "eidboaoo" has no match either way.
Score 60% or more and the lesson is marked complete.