Permutation in String
Medium · Sliding Window · Explanation and code example
Sliding Window
How it works
Since a permutation of s1 must have the same character counts, we can use a fixed-size sliding window over s2 whose length is exactly len(s1).
We maintain two frequency arrays:
- one for
s1 - one for the current window in
s2
If these two arrays ever match, the window is a valid permutation. As we slide the window forward, we update counts by removing the left character and adding the new right character — no need to rebuild the counts each time. This makes the solution fast and efficient.
Steps
- If
s1is longer thans2, returnfalse. - Build character frequency arrays for:
s1- the first window of
s2of sizelen(s1)
- Count how many positions match between the two arrays (
matches). - Slide the window from left to right across
s2:- At each step, add the new right character and update counts/matches.
- Remove the left character and update counts/matches.
- If at any time
matches == 26, returntrue.
- After finishing the loop, return whether
matches == 26.
Complexity
- Time complexity:
O(n) - Space complexity:
O(1)
Things to watch for
Not Checking Length Before Proceeding
If s1 is longer than s2, no permutation of s1 can exist as a substring of s2. Forgetting this early check leads to unnecessary computation or index errors when initializing the sliding window.
Incorrect Window Size
The sliding window must be exactly the length of s1. A common mistake is using a variable-size window or forgetting to remove the leftmost character when adding a new right character. This breaks the frequency comparison and produces incorrect results.
Mishandling the Matches Counter
When updating the frequency counts during window sliding, the matches counter must be carefully updated. A character transition from matching to non-matching should decrement matches, and vice versa. Off-by-one errors in these conditions (e.g., checking == vs +1 or -1) cause the algorithm to miss valid windows or report false positives.
Python code example
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
if len(s1) > len(s2):
return False
s1Count, s2Count = [0] * 26, [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):
matches += (1 if s1Count[i] == s2Count[i] else 0)
l = 0
for r in range(len(s1), len(s2)):
if matches == 26:
return True
index = ord(s2[r]) - ord('a')
s2Count[index] += 1
if s1Count[index] == s2Count[index]:
matches += 1
elif s1Count[index] + 1 == s2Count[index]:
matches -= 1
index = ord(s2[l]) - ord('a')
s2Count[index] -= 1
if s1Count[index] == s2Count[index]:
matches += 1
elif s1Count[index] - 1 == s2Count[index]:
matches -= 1
l += 1
return matches == 26
C++ code example
class Solution {
public:
bool checkInclusion(string s1, string s2) {
if (s1.length() > s2.length()) {
return false;
}
vector<int> s1Count(26, 0);
vector<int> s2Count(26, 0);
for (int i = 0; i < s1.length(); i++) {
s1Count[s1[i] - 'a']++;
s2Count[s2[i] - 'a']++;
}
int matches = 0;
for (int i = 0; i < 26; i++) {
if (s1Count[i] == s2Count[i]) {
matches++;
}
}
int l = 0;
for (int r = s1.length(); r < s2.length(); r++) {
if (matches == 26) {
return true;
}
int index = s2[r] - 'a';
s2Count[index]++;
if (s1Count[index] == s2Count[index]) {
matches++;
} else if (s1Count[index] + 1 == s2Count[index]) {
matches--;
}
index = s2[l] - 'a';
s2Count[index]--;
if (s1Count[index] == s2Count[index]) {
matches++;
} else if (s1Count[index] - 1 == s2Count[index]) {
matches--;
}
l++;
}
return matches == 26;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.