Medium Fixed Window Sliding Window
In plain English: Check if any rearrangement of s1 appears as a contiguous chunk inside s2.
Use a fixed-size sliding window equal to len(s1). Maintain a frequency count difference — when all counts are zero, you've found a permutation. Slide one char at a time, adding right and removing left.
Prompt
Given two strings s1 and s2, return True if s2 contains a permutation of s1 (i.e., one of s1's permutations is a substring of s2).
Try to write it from scratch before scrolling down.
Solution
def check_inclusion(s1, s2):
if len(s1) > len(s2):
return False
from collections import Counter
need = Counter(s1)
window = Counter(s2[:len(s1)])
if window == need:
return True
for i in range(len(s1), len(s2)):
# add right char
window[s2[i]] += 1
# remove left char
left = s2[i - len(s1)]
window[left] -= 1
if window[left] == 0:
del window[left]
if window == need:
return True
return False
# Test: check_inclusion("ab", "eidbaooo") == True ("ba" is permutation)
# Test: check_inclusion("ab", "eidboaoo") == False