Permutation in String
Medium· fixed window· frequency count
Problem
Determine whether s2 contains some rearrangement of s1 as a contiguous substring. In other words, check if any window of s2 is an anagram of s1.
Examples
Input: s1 = "ab", s2 = "eidbaooo"
Output: true
s2 contains "ba", which is a permutation of "ab".
Input: s1 = "ab", s2 = "eidboaoo"
Output: false
Constraints
- • 1 <= s1.length, s2.length <= 10^4
- • Lowercase English letters only
Hints & approach
Hint 1
Any matching window has exactly the length of s1.
Hint 2
Compare letter counts of the window with those of s1.
Hint 3
Update counts incrementally as the window slides, and track how many letters currently match.
Approachtry the hints first
Build a 26-count array for s1, and another for the first len(s1) characters of s2. Slide a fixed-size window across s2, adding the incoming character and removing the outgoing one. Maintain a counter of how many of the 26 letters have equal counts in both arrays; when all 26 match, a permutation has been found. Each slide updates only two letters, so the scan is linear.
Time O(n) · Space O(1) (26 counters)