Permutation in String
Permutation in String: given two strings s1 and s2, return true if s2 contains a permutation of s1 as a contiguous substring.
- 1 <= s1.length, s2.length <= 10⁴
- s1 and s2 consist of lowercase English letters.
Intuition
Permutation in string asks whether any permutation of s1 appears as a contiguous substring of s2. Generating permutations is factorial and hopeless; the reframing is what makes it linear.
A permutation of s1 is any arrangement of exactly its characters, so:
- A substring is a permutation of s1 precisely when it has the same length and the same character frequencies — order is irrelevant.
Equal length means only windows of length s1.length can match, which fixes the window size and turns this into a sliding-window frequency comparison.
Build a frequency count for s1, then slide a window of that length across s2, updating counts as characters enter and leave. When the two counts match, a permutation has been found.
Comparing two 26-element arrays at each position is O(26) per window — constant, and perfectly acceptable.
The faster version keeps a matches counter: how many of the 26 letters currently have exactly the right count. A window matches when that reaches 26. Updating it correctly requires checking whether a count became correct or stopped being correct with each change, comparing before and after. Testing only one side leaves the counter permanently wrong.
The window slides by two operations — decrement the outgoing character, increment the incoming — so each step is O(1) regardless of window size.
If s1 is longer than s2, no window exists and the answer is false immediately.
This is the same machinery as Find All Anagrams in a String, which returns every match rather than just whether one exists.
A fixed-width window plus a matches counter that tracks how many distinct characters have hit their exact required count. Comparing one integer against the number of needed characters replaces re-comparing two frequency maps every step.
Approach
Before reading on: price up what counting everything costs here, then ask what makes a window invalid, and which pointer should move when it is. Aim for O(n) time and O(1) space.
Reframe permutations as frequencies
A permutation is any arrangement of the same characters, so equal length plus equal frequencies is the whole test — order never matters.
Fix the window size
Only windows of length s1.length can match. If s1 is longer than s2, return false immediately — no valid window exists.
Build the target counts
Count each character in s1. A window matches when its own counts equal these exactly.
Slide with two updates
Decrement the outgoing character and increment the incoming one. Each step is O(1), independent of the window's size.
Compare counts per window
With a 26-letter alphabet, comparing the arrays is O(26) — constant. This version is simple and fast enough for any input here.
Or track a matches counter
Count letters whose frequency is exactly right, matching at 26. Check whether each change made a letter correct or broke it — testing one side leaves the counter wrong.
Cost of the scan
Each character enters and leaves once, giving O(n) time with the counter or O(26n) with array comparison, and O(1) space for the fixed alphabet.
Solution & live demo
Common pitfalls
Comparing full frequency maps each step
if have == need: return True
if matches == need_keys: return True
Dictionary comparison is O(26) per position, turning the scan into O(26n). Tracking transitions to and from the exact count makes each step O(1).
Decrementing matches unconditionally on removal
have[left_ch] -= 1 matches -= 1
if have[left_ch] == need.get(left_ch, 0):
matches -= 1
have[left_ch] -= 1Removing a surplus copy, or a character not in s1 at all, doesn't break a satisfied requirement. The counter should only fall when a character leaves its exact-match state, which is tested before the decrement.
Checking the answer before the window is full
if matches == need_keys: return True
if r >= k - 1 and matches == need_keys:
Early in the scan the window is shorter than s1, so a coincidental match on a prefix reports a permutation that isn't one. The width guard ensures a full-size window.
Edge cases
No window of that width fits in s2, so the loop never reaches full width and the answer is false; guard against this or let the loop naturally produce zero valid windows.
The single full-width window is trivially a permutation of itself, so matches reaches the needed count on the last character processed.
The need map naturally holds counts greater than 1 for repeated letters; the matches-counter approach still works since equality is checked per distinct key, not per occurrence.
Every window's matches count stays below the needed total, and the function correctly returns false after scanning the whole string.