Permutation in String
01 · Problem
Given two strings s1 and s2, return true if some contiguous substring of s2 is a rearrangement (permutation) of s1, and false otherwise.
In other words, determine whether s2 contains a window of length s1.length that uses exactly the same letters as s1, with the same multiplicities, in any order. If s1 is longer than s2, the answer is false.
02 · Examples
s1 = "xy", s2 = "pqyxr"
true
The substring "yx" starting at index 2 is a permutation of "xy".
s1 = "xy", s2 = "pxqyr"
false
"x" and "y" never sit next to each other, so no window of length 2 contains exactly one of each.
s1 = "tea", s2 = "sweatyx"
true
The window "eat" starting at index 2 uses the letters t, e and a once each.
03 · Constraints
- 011 <= s1.length <= 104
- 021 <= s2.length <= 104
- 03s1 and s2 consist of lowercase English letters
- 04s1.length may exceed s2.length, in which case the answer is false
04 · Optimal complexity
- Time
- O(n)
- Space
- O(1)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.