Permutation in String
Solve and submit on LeetCode to build your LeetCode profile. Use the hints here when you need guidance.
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
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)
