Permutation in String
Given two strings s1 and s2, return true if s2 contains a permutation of s1 as a contiguous substring.
Open on LeetCode ↗Intuition
The trap is re-sorting or re-counting the whole window's characters at every slide, which is O(n * k log k) or worse -- it throws away work you already did on the previous window. The window here is a FIXED width, exactly len(s1), so as it slides by one position exactly one character enters on the right and exactly one leaves on the left. Update two running counts instead of recomputing from scratch: bump the entering character up, bump the leaving character down. You can go one step further and avoid even comparing 26 count buckets every time -- keep a single matches counter that tracks how many characters currently have the exact count s1 needs, and only increment or decrement it when a bump causes a count to enter or leave equality with the target. Then checking whether the window is a permutation is just matches == number of needed keys, an O(1) comparison instead of a scan.
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
Build the target count map once
Count the letters of s1 into a need map. This never changes for the rest of the algorithm -- it's the fixed target every window is compared against.
Slide a fixed-width window with running counts
Walk s2 with a right pointer. Add the entering character to a have map; once the window has grown past width len(s1), also remove the character leaving on the left. Never rebuild have from scratch.
Track a matches counter for O(1) comparison
Whenever a bump makes a character's count in have equal its count in need, increment matches; whenever a bump moves a count away from that equality, decrement matches. The window is a permutation of s1 exactly when matches equals the number of distinct keys in need.
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.