LeetCode · #567
Permutation in String Solution
Given two strings s1 and s2, return true if s2 contains a permutation of s1.
01
Section One · Problem
Problem Statement
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 "ba" which is a permutation of "ab"
Example 2
Input: s1 = "ab", s2 = "eidboaoo" Output: false // No substring of length 2 in s2 has the same character frequencies as "ab"
Constraints
• 1 ≤ s1.length, s2.length ≤ 10⁴ • s1 and s2 consist of lowercase English letters
02
Section Two · Approach 1
Brute Force — Sort Every Window
Slide a window of size len(s1) over s2. For each window, sort the characters and compare with sorted s1. If they match, it's a permutation.
Problem: Sorting each window costs O(k log k) where k = len(s1), repeated ~n times → O(n·k log k). A frequency array comparison replaces sorting with O(26) = O(1) per slide.
Java — Sort & Compare
import java.util.Arrays;
class Solution {
public boolean checkInclusion(String s1, String s2) {
char[] target = s1.toCharArray();
Arrays.sort(target);
for (int i = 0; i <= s2.length() - s1.length(); i++) {
char[] window = s2.substring(i, i + s1.length()).toCharArray();
Arrays.sort(window);
if (Arrays.equals(target, window)) return true;
}
return false;
}
}
Python — Sort & Compare
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
target = sorted(s1)
k = len(s1)
for i in range(len(s2) - k + 1):
if sorted(s2[i:i + k]) == target:
return True return False
| Metric | Value |
|---|---|
| Time | O(n · k log k) |
| Space | O(k) |
03
Section Three · Approach 2
Fixed-Size Sliding Window — O(n)
Build a frequency array for s1. Slide a window of size len(s1) across s2, maintaining a window frequency array. When the window slides, add the new right character and remove the old left character. If both frequency arrays match → permutation found.
💡 Mental model: You have a cookie cutter (s1's frequency signature) and a long strip of dough (s2). You slide the cutter one position at a time. At each position, you check if the dough under the cutter has the exact same ingredient distribution. Instead of re-measuring from scratch, you update the counts: add the new ingredient entering on the right, remove the one leaving on the left.
Algorithm
- Step 1: Build
s1Count[26]from s1. - Step 2: Build
s2Count[26]from the firstlen(s1)characters of s2. Compare. - Step 3: Slide the window: add
s2[right], removes2[right - len(s1)]. - Step 4: After each slide, compare the 26-element arrays. If equal → return true.
- Step 5: Track a
matchescounter (how many of the 26 slots agree) to avoid comparing all 26 each time.
🎯 Matches counter optimization:
- Instead of comparing all 26 slots each slide, maintain a
matchescount. - When adding/removing a character changes a slot from equal→unequal, decrement matches.
- When it goes unequal→equal, increment. If
matches == 26, we have a permutation. - This makes each slide O(1) instead of O(26).
04
Section Four · Trace
Visual Walkthrough
Trace through s1 = "ab", s2 = "eidbaooo":
Fixed Window — slide window of size 2 across s2
05
Section Five · Implementation
Code — Java & Python
Java — Sliding Window with matches counter
class Solution {
public boolean checkInclusion(String s1, String s2) {
if (s1.length() > s2.length()) return false;
int[] s1Count = new int[26], s2Count = new int[26];
for (int i = 0; i < s1.length(); i++) {
s1Count[s1.charAt(i) - 'a']++;
s2Count[s2.charAt(i) - 'a']++;
}
int matches = 0;
for (int i = 0; i < 26; i++)
if (s1Count[i] == s2Count[i]) matches++;
for (int r = s1.length(); r < s2.length(); r++) {
if (matches == 26) return true;
int addIdx = s2.charAt(r) - 'a'; // entering char
s2Count[addIdx]++;
if (s2Count[addIdx] == s1Count[addIdx]) matches++;
else if (s2Count[addIdx] == s1Count[addIdx] + 1) matches--;
int remIdx = s2.charAt(r - s1.length()) - 'a'; // leaving char
s2Count[remIdx]--;
if (s2Count[remIdx] == s1Count[remIdx]) matches++;
else if (s2Count[remIdx] == s1Count[remIdx] - 1) matches--;
}
return matches == 26;
}
}
Python — Sliding Window with matches counter
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
if len(s1) > len(s2): return False
s1_count = [0] * 26
s2_count = [0] * 26 for i in range(len(s1)):
s1_count[ord(s1[i]) - ord('a')] += 1
s2_count[ord(s2[i]) - ord('a')] += 1
matches = sum(1 for i in range(26) if s1_count[i] == s2_count[i])
for r in range(len(s1), len(s2)):
if matches == 26: return True
idx = ord(s2[r]) - ord('a')
s2_count[idx] += 1 if s2_count[idx] == s1_count[idx]: matches += 1 elif s2_count[idx] == s1_count[idx] + 1: matches -= 1
idx = ord(s2[r - len(s1)]) - ord('a')
s2_count[idx] -= 1 if s2_count[idx] == s1_count[idx]: matches += 1 elif s2_count[idx] == s1_count[idx] - 1: matches -= 1 return matches == 26
06
Section Six · Analysis
Complexity Analysis
| Approach | Time | Space | Trade-off |
|---|---|---|---|
| Sort every window | O(n · k log k) | O(k) | Rebuilds sorted window each slide |
| Array compare each slide | O(26n) | O(1) | Compares all 26 slots per slide |
| Matches counter ← optimal | O(n) | O(1) | O(1) per slide; tracks matching slots incrementally |
07
Section Seven · Edge Cases
Edge Cases & Pitfalls
| Case | Input | Why It Matters |
|---|---|---|
| s1 longer than s2 | s1="abc", s2="ab" | Impossible — return false immediately. |
| Exact match | s1="abc", s2="abc" | The entire s2 is a permutation of s1 → true. |
| Single char | s1="a", s2="a" | Trivial match. |
| No overlap | s1="ab", s2="ccc" | None of s1's characters exist in s2 → false. |
| Permutation at end | s1="ab", s2="xxxba" | Match at the last window position. Must check the final window. |
⚠ Common Mistake: Forgetting to check
matches == 26 after the loop ends. The last window position is processed inside the loop body, but the final check happens only when returning. Always return matches == 26 at the end to catch a match at the last position.