Permutation in String
Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.
In other words, return true if one of s1's permutations is a substring of s2.
Example 1:
Input:s1 = "ab", s2 = "eidbaooo"
Output:true
s2 contains one permutation of s1 ("ba").
Example 2:
Input:s1 = "ab", s2 = "eidboaoo"
Output:false
Constraints:
- 1 ≤ s1.length, s2.length ≤ 10⁴
- s1 and s2 consist of lowercase English letters.
Two strings are permutations of each other if and only if their character frequency arrays are equal. For lowercase English letters, that means 26 integer counts.
Maintain a window of size len(s1) over s2. As the window slides, add the new right character and remove the old left character. Update counts incrementally — O(1) per slide.
Keep a counter of how many of the 26 letter positions have equal counts in s1 and the current window. When you add/remove a character, update only the affected position. If matches == 26, you found a permutation.
🌐 Real-World Analogy
Anagram Spell Checker
A word game engine checks whether any rearrangement of a short pattern word appears in a long text. Instead of generating all permutations (factorial time!), it slides a window of the same length across the text and compares letter frequency profiles. The sliding window with a matches counter makes this O(n) — critical when scanning millions of game boards per second.
Optimal Approach — Fixed Sliding Window + Frequency Matching
O(n) TimeA permutation of s1 must have the same length and the same character frequencies. We slide a fixed-size window over s2 and use a matches counter to track how many of the 26 character positions have equal counts.
- 1Build frequency arrays
count1 (for s1) and count2 (first window of s2). Compute initial matches. - 2Slide the window: add the new right character, update
matches for that character position. - 3Remove the old left character, update
matches for that character position. - 4If
matches == 26 at any point, return True. - 5After the loop, check once more. If still not 26, return
False.
Each character addition/removal only modifies one of the 26 positions, so updates are O(1). Total complexity: O(n) time, O(1) space (only 52 integers).
s2 — Sliding Window
s1Count vs s2Count (sliding window)
READY—
Press ▶ or step forward to begin.s1—
window—
matches—
result—
Space Play/Pause·←→ Step·R Reset
Executing Code
def checkInclusion(self, s1, s2):
if len(s1) > len(s2): return False
s1Count = [0] * 26
s2Count = [0] * 26
for i in range(len(s1)):
s1Count[ord(s1[i]) - ord('a')] += 1
s2Count[ord(s2[i]) - ord('a')] += 1
matches = 0
for i in range(26):
if s1Count[i] == s2Count[i]: matches += 1
l = 0
for i in range(len(s1), len(s2)):
if matches == 26: return True
index = ord(s2[i]) - ord('a')
s2Count[index] += 1
if s2Count[index] == s1Count[index]: matches += 1
elif s2Count[index] != s1Count[index]: matches -= 1
index = ord(s2[l]) - ord('a')
s2Count[index] -= 1
if s2Count[index] == s1Count[index]: matches += 1
elif s2Count[index] != s1Count[index]: matches -= 1
l += 1
return matches == 26
Discussion
…