Permutation in String
Problem statement
You are given two strings, s1 and s2. Return true if some rearrangement
of s1's letters — a permutation of s1 — appears as a contiguous chunk
inside s2, and false otherwise.
In other words: is there a window in s2, the same length as s1, that uses
exactly the same letters as s1, the same number of times each, just
possibly in a different order?
Examples
Example 1
Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1, the substring "ba",
Example 2
Input: s1 = "ab", s2 = "eidboaoo"
Output: false
Explanation: No two-letter window of s2 uses exactly one a and one
Hints
s1 inside s2 just means: some window of s2, the
same length as s1, uses exactly the same letters, the same number of
times each — order doesn't matter.Approach
Optimal: Sliding window with counts maintained incrementally
Intuition
Between one window and the very next one, almost nothing changes: the
leftmost letter leaves, one new letter joins on the right, and every other
count stays exactly the same. Rebuilding the whole window from scratch, like
Better does, throws away and redoes that unchanged work every single step.
Instead, keep one running count array and just update it — subtract the
letter that's leaving, add the letter that's arriving — then compare it to
need. That turns the O(m) rebuild into an O(1) update, which is what makes
this approach linear instead of O(n · m).
Steps
- If
s2is shorter thans1, returnfalse. Letm = len(s1). - Build
need, a 26-slot count of the letters ins1. - Build
window, a 26-slot count of the firstmcharacters ofs2. - If
windowalready equalsneed, returntrue. - For each index
ifrommtolen(s2) - 1:- Add
s2[i]towindow— the letter entering on the right. - Remove
s2[i - m]fromwindow— the letter leaving on the left. - If
windowequalsneed, returntrue.
- Add
- If nothing matched by the end, return
false.
Dry run
s1 = "ab" (so m = 2, need = {a: 1, b: 1}), s2 = "eidbaooo"
| step | window before | letter added (right) | letter removed (left) | window after | matches need? |
|---|---|---|---|---|---|
| build | — | s2[0..1] = "ei" |
— | {e:1, i:1} |
no |
i=2 |
{e:1, i:1} |
s2[2] = 'd' |
s2[0] = 'e' |
{i:1, d:1} |
no |
i=3 |
{i:1, d:1} |
s2[3] = 'b' |
s2[1] = 'i' |
{d:1, b:1} |
no |
i=4 |
{d:1, b:1} |
s2[4] = 'a' |
s2[2] = 'd' |
{a:1, b:1} |
yes → return true |
The window itself moves "ei" → "id" → "db" → "ba" across s2, and "ba"
at the last step is exactly the permutation of "ab" the example points to.
Edge cases: if s1 is longer than s2, step 1 catches it before any counting
happens. If s1 has a repeated letter (like "aab"), the count comparison
still works correctly, since it checks exact counts per letter, not just
which letters are present.
Complexity
Time O(n) - the window slides forward one letter at a time. At each step, exactly one letter leaves and one enters, so updating the counts is O(1); comparing two 26-length arrays is O(26), a constant. There are about `n` slides in total, so the whole scan is O(n).
Space O(1) - the same two fixed 26-slot count arrays as Better.
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
m, n = len(s1), len(s2)
if m > n:
return False
need = [0] * 26
window = [0] * 26
for ch in s1:
need[ord(ch) - ord('a')] += 1
for ch in s2[:m]:
window[ord(ch) - ord('a')] += 1
if window == need:
return True
for i in range(m, n):
window[ord(s2[i]) - ord('a')] += 1
window[ord(s2[i - m]) - ord('a')] -= 1
if window == need:
return True
return False
if __name__ == "__main__":
print(str(Solution().checkInclusion("ab", "eidbaooo")).lower()) # true
print(str(Solution().checkInclusion("ab", "eidboaoo")).lower()) # falseRecapThe whole problem in a few lines, for the night before
- Spot it: does s2 contain any permutation of s1 as a substring
- Idea: fixed window of length len(s1) over s2 with letter counts; if the window counts equal s1's counts, return true
- Cost: O(n) time, O(1) space (26 letters)
- Trap: the window must be contiguous and exactly len(s1) long; it is not a subsequence
Interview follow-ups
Return the starting index of the first matching window instead of
true/false.Track the index instead of returning a boolean: return
0when the very first window (built before the loop) matches, and returni - m + 1when a later window matches inside the loop, sinceiis the index of the letter that just entered on the right. Return-1if the loop finishes with no match. Same O(n) time.Find every starting index where a permutation of
s1occurs, not just the first.Don't return as soon as one match is found — instead, append its starting index to a results list and keep sliding the window all the way to the end of
s2. The time complexity stays O(n), since the window still only takes one O(1) step per position; only the amount of output can grow.What if the strings could contain uppercase letters or characters beyond
a–z?Swap the fixed 26-slot arrays for a hash map keyed by character, and keep the exact same sliding logic — add the entering character, remove the leaving one, compare the two maps. The time complexity stays O(n), but a hash map lookup is O(1) only on average, unlike a fixed-size array's guaranteed O(1).
Frequently asked questions
Because that's what a permutation is: a rearrangement of the same letters. Two
strings use the same letters the same number of times if and only if one can
be reordered into the other. So once the counts match exactly, the order
inside the window is irrelevant — some arrangement of s1 is sitting right
there.
The question asks whether a permutation of s1 — meaning a string the exact
same length as s1 — shows up inside s2. Every window checked is exactly
len(s1) characters long, since a shorter or longer window could never be a
rearrangement of s1. That's also why the function returns false
immediately when s1 is longer than s2: no window of that size can even
exist.
The same shape shows up when you need an exact multiset match inside a
stream — for example, checking whether a fixed set of required resource tags
(say, two gpu allocations and one ssd) ever appears together in a
contiguous stretch of a longer allocation log, regardless of the order they
were requested in.
All three slide a window across a string and keep small letter counts, but
the rule for "is this window good?" is different each time. Here, the window
must match s1's counts exactly. Longest Repeating Character Replacement
allows a window to be close enough — off by at most k changes. Longest
Substring Without Repeating Characters asks for no letter to repeat at all,
with no fixed target to match against.
