Permutation in String
MediumFixed window, compare frequency counts
Problem
Return whether s2 contains a permutation of s1 as a substring.
Slide a fixed-size window and check if its letter counts match the pattern's counts.
The idea
A permutation of s1 is any window of s1's length whose character counts match s1's. Slide a window of that exact size and keep a running match tally so each step is O(1) rather than a 26-way comparison.
The trick
- The window size is fixed at s1.length — this is not a variable window.
- Track how many of the 26 counts currently agree, updating on the two changed characters only.
- O(n) time, O(1) space.
e
i
d
b
a
o
o
o
0
1
2
3
4
5
6
7
Step 1 of 5. Brute force: check every window of length 2 against "ab". Values: e, i, d, b, a, o, o, o.
1/5
Brute force
timeO(n·k)spaceO(1)
Check every window.
1for (let i = 0; i + k <= n; i++)2 if (sameCounts(s2.slice(i, i + k), s1)) return true;3return false;Input
- array
- [e, i, d, b, a, o, o, o]
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- s1 = "ab", s2 = "eidbaooo"
- Output:
- true
- Explanation:
- "ba" is a permutation of "ab" inside s2.
Example 2
- Input:
- s1 = "ab", s2 = "eidboaoo"
- Output:
- false
- Explanation:
- No ab/ba window → false.
Example 3
- Input:
- s1 = "a", s2 = "a"
- Output:
- true
- Explanation:
- Exact single-letter match.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.