Permutation in String
Problem Statement
Given two strings s1 and s2, return true if s2 contains a permutation of s1. In other words, some contiguous substring of s2 must contain exactly the same character counts as s1.
Input
Two lowercase strings s1 and s2. The target permutation length is s1.length.
Output
A boolean: true if any length-s1.length substring of s2 is an anagram of s1, otherwise false.
Constraints
- •
1 <= s1.length, s2.length <= 10^4 - •
s1 and s2 consist of lowercase English letters
Examples
Example 1
s1 = ab, s2 = eidbaooo
trueExample 2
s1 = ab, s2 = eidboaoo
falseExample 3
s1 = adc, s2 = dcda
trueLearning Objectives
- Recognise permutation-in-string as fixed-window anagram matching.
- Maintain character frequencies incrementally instead of rebuilding each substring.
- Use a match counter to compare two frequency arrays in O(1) per slide.
- Handle the impossible case where the target is longer than the search string.
Intuition
This is a Pattern Identification problem: the answer must be a contiguous substring of s2, and its length is fixed at s1.length. Any permutation of s1 has exactly the same frequency count for every lowercase letter, so order inside the window does not matter; counts do.
The tempting slow approach is to sort every candidate substring or rebuild a fresh frequency table for every start index. The sliding-window insight is that adjacent windows differ by only two characters: one leaves on the left and one enters on the right. Update those two counts, then test whether the window frequency equals the target frequency.
Common mistakes
- ×Checking only whether the same set of letters appears, which ignores duplicate counts.
- ×Sorting every window and turning a linear scan into extra logarithmic work.
- ×Forgetting to remove the leftmost character when the fixed window moves.
- ×Not returning **false** immediately when **s1.length > s2.length**.
Algorithm Explanation
Window setup
Use two length-26 arrays: targetCount for s1 and windowCount for the current length-s1.length window in s2. Keep matches, the number of character slots where the two arrays currently agree. When matches == 26, the current window is a permutation.
Window visualization
For s1 = ab and s2 = eidbaooo, the target has a:1 and b:1. The first window ei has e:1 and i:1, so the important counts do not match. Slide to id, then db. At db, b matches but a is still missing. When the window becomes ba at indices 3..4, the window has a:1 and b:1, so every character slot matches the target.
Algorithm
- If s1 is longer than s2, return false.
- Build frequency arrays for s1 and for the first s1.length characters of s2.
- Count how many of the 26 character positions currently match.
- If all 26 match, return true.
- Slide the fixed-size window one character at a time: add the entering character and remove the leaving character, adjusting matches before and after each count change.
- Return true as soon as matches == 26; otherwise return false after the scan.
Solutions
Solution: Fixed window with a character match counter
The frequency arrays represent the target and the current window. Instead of comparing all 26 entries after every slide, maintain matches, the number of positions already equal. Updating one character count can only affect that character position, so each slide stays O(1).
Step-by-step
- Reject the case where s1 is longer than s2.
- Fill targetCount from s1 and windowCount from the first window of s2.
- Initialise matches by comparing all 26 slots once.
- For each new right index, add the entering character and update matches around that count change.
- Remove the character that fell out of the fixed window and update matches around that count change.
- If matches reaches 26 at any point, the current window is a permutation.
O(n + 26)
O(1)
The scan touches each character of s2 once, and the arrays have fixed alphabet size 26.
Java implementation
Dry Run
Sample input
s1 = ab, s2 = eidbaooo. The window size is 2 and the target counts are a:1, b:1.
| step | window bounds | entering | leaving | important window counts | matches | decision |
|---|---|---|---|---|---|---|
| initial | 0..1 | none | none | e:1, i:1 | 22 | Not a match. |
| slide 1 | 1..2 | d | e | d:1, i:1 | 22 | Still missing both a and b. |
| slide 2 | 2..3 | b | i | b:1, d:1 | 24 | b matches, but a is missing. |
| slide 3 | 3..4 | a | d | a:1, b:1 | 26 | All counts match, return true. |
The first time matches reaches 26 is the window ba, which is a valid permutation of ab.
Interview Tips
Name the pattern early: this is fixed-window anagram matching. Emphasise that permutations are about counts, not order. A strong answer either compares 26-count arrays at each step or maintains a match counter; the match counter is a nice senior-level refinement because it makes the per-slide equality check explicit and constant time.
Likely follow-ups
- How would you adapt this if the alphabet were full Unicode instead of lowercase English letters?
- How would you return the first matching index instead of a boolean?
- What changes if **s1** can contain uppercase and lowercase letters separately?
- Could you solve it with a single balance array instead of two arrays?
Similar Problems
Key Takeaways
- Permutation matching over a string is fixed-window anagram matching.
- A length-26 frequency array captures all lowercase character counts.
- Adjacent windows differ by one entering and one leaving character.
- A match counter avoids rescanning the whole frequency array after every slide.