LeetCode 567 · Sliding Window · concept: sliding-window
Problem
Return true if s2 contains a permutation of s1 as a contiguous substring.
s1 = "ab", s2 = "eidbaooo" -> true ("ba")
s1 = "ab", s2 = "eidboaoo" -> false
Approach — fixed-size window, compare char counts (optimal)
A permutation of s1 is any substring of length len(s1) with the same character counts. So slide a window of exactly that width across s2 and check whether its count vector matches s1’s.
from collections import Counter
def checkInclusion(s1, s2):
if len(s1) > len(s2):
return False
need = Counter(s1)
window = Counter(s2[:len(s1)])
if window == need:
return True
for r in range(len(s1), len(s2)):
window[s2[r]] += 1 # add the new right char
left = s2[r - len(s1)]
window[left] -= 1 # drop the char leaving on the left
if window[left] == 0:
del window[left] # keep Counters comparable
if window == need:
return True
return FalseTime O(n), space O(1) (26-letter counts). This is a fixed-size window — unlike the variable windows above, the width never changes; you add one char and remove one each step.
Optimization to O(1) per step
Comparing two Counters is O(26). To make each step true O(1), track a matches counter of how many of the 26 letters currently have equal counts, updating it incrementally as chars enter/leave — the answer is found when matches == 26.
Key insight
“Contains a permutation / anagram of X” → fixed-width window + character-count equality. Anagram = equal multiset (Valid Anagram); sliding a fixed window turns “is there an anagram anywhere” into a rolling count comparison.
Related
- concept: sliding-window; builds on Valid Anagram
- prev: Longest Repeating Character Replacement · next: Minimum Window Substring
Software engineering
Infrastructure & security
Computer science
Hardware & engineering