Permutation in String
Check whether some rearrangement of a short string appears as a block of neighbouring letters inside a longer string.
- Fixed-size sliding window
- Frequency matching
Before this, know: Counting letters (Valid Anagram, week 1), Sliding window
You get two strings of lowercase letters, s1 and s2. A permutation of
s1 is any rearrangement of its letters: the permutations of "ab" are "ab"
and "ba".
Return true if some permutation of s1 appears inside s2 as a
substring (letters sitting next to each other), and false otherwise.
Example: s1 = "ab", s2 = "eidbaooo".
- e0
- i1
- d2
- b3
- a4
- o5
- o6
- o7
The rules that matter:
- The matching block in
s2must have exactlylen(s1)letters, all next to each other. - Only lowercase
atoz. - If
s1is longer thans2, the answer isfalse.
In week 1’s Valid Anagram we learned that two words are rearrangements of each
other (anagrams) exactly when they contain the same letters the same number
of times. So “is this block a permutation of s1?” is the same question as
“does this block have the same letter counts as s1?”
| a | b | |
|---|---|---|
| need (s1) | 1 | 1 |
| have (window) | 1 | 1 |
Pause and think
d (index 2) leaves and a (index 4) enters. The new window is "ba".
To update the counts we only touch two numbers: d goes down by 1, a goes up
by 1. The b in the middle never changes.
The truly naive idea is to list every permutation of s1 and search for each one
in s2. That falls apart fast: a 10-letter s1 has 10 × 9 × … × 1 = 3,628,800
permutations.
A better first attempt: sorting a word puts its letters in alphabetical order, and
two words are rearrangements exactly when their sorted versions are equal
("ba" → "ab"). So sort s1 once, then sort every len(s1)-letter window of
s2 and compare.
Sort every window
s1 = "ab", s2 = "eidbaooo"
- e0
- i1
- d2
- b3
- a4
- o5
- o6
- o7
- sorted(s1)
- ab
- sorted(window)
- —
- same?
- —
- Current window
- Permutation found
Sort s1's letters once: "ab" becomes "ab". Any rearrangement of s1 also sorts to "ab".
Which line is running?
function checkInclusion(s1, s2) { const sorted = (text) => text.split("").sort().join("");Running now: const target = sorted(s1); for (let start = 0; start + s1.length <= s2.length; start++) { const window = s2.slice(start, start + s1.length); if (sorted(window) === target) return true; } return false;}Sort every window
function checkInclusion(s1, s2) { const sorted = (text) => text.split("").sort().join(""); const target = sorted(s1); for (let start = 0; start + s1.length <= s2.length; start++) { const window = s2.slice(start, start + s1.length); if (sorted(window) === target) return true; } return false;}def check_inclusion(s1, s2): target = sorted(s1) for start in range(len(s2) - len(s1) + 1): window = s2[start:start + len(s1)] if sorted(window) == target: return True return FalseLet m be the length of s1 and n the length of s2. There are about n
windows, and sorting each one takes about m × log m steps. Here log m is roughly
how many times you can halve m before reaching 1: about 10 for m = 1,000, so
sorting costs about 10 steps per letter. So the total is about
n × m × log m. With n = 10,000 and m = 1,000 (LeetCode’s limits allow
up to 10,000 each), that’s about 10,000 × 1,000 × 10 = 100 million steps.
In Big-O notation (a short way of saying how the work grows as the input
grows; see Big-O in 5 minutes) that’s
O(n · m log m). Each window is sorted
from scratch, even though it shares all but one letter with the previous window.
Unlike the last two problems, the window never grows or shrinks: both edges move together, one step at a time.
Pattern
Fixed-size sliding window
Use it when: the answer is about blocks of exactly k neighbouring items (k is given or is the length of another string).
Signal words
- “permutation of s1 in s2”
- “anagram substring”
- “window of size k”
- “contains a rearrangement”
- “every k consecutive”
- If
s1is longer thans2, returnfalse. - Make two lists of 26 counts (one slot per letter a–z):
needfors1andhavefor the firstlen(s1)letters ofs2. - If
needequalshave, returntrue. - Slide the window one letter at a time: add 1 to the count of the letter entering on the right, subtract 1 from the letter leaving on the left.
- After each slide, compare again. If they’re equal, return
true. - If the window reaches the end without a match, return
false.
The table under the string compares the two counts letter by letter: green
columns match, red ones differ, violet just changed. The answer is true
the moment every column is green.
Fixed-size window with letter counts
s1 = "ab", s2 = "eidbaooo"
- a0
- b1
- e0
- i1
- d2
- b3
- a4
- o5
- o6
- o7
| need (s1) |
|---|
| have (window) |
- window size
- 2
- counts equal?
- —
- result
- —
- Inside the window
- Just entered / its count changed
- Just left
- Count matches
- Count differs
- Permutation found
A permutation of "ab" is any rearrangement of its letters. Two strings are rearrangements of each other exactly when they have the same letter counts. So: count s1's letters ("need"), then slide a window of exactly 2 letters over s2 and compare its counts ("have").
Which line is running?
function checkInclusion(s1, s2) {Running now: if (s1.length > s2.length) return false; const need = new Array(26).fill(0); // letter counts of s1 const have = new Array(26).fill(0); // letter counts of the window const idx = (ch) => ch.charCodeAt(0) - 97; // 'a' -> 0, 'b' -> 1, ... 'z' -> 25 for (let i = 0; i < s1.length; i++) { need[idx(s1[i])]++; have[idx(s2[i])]++; } if (sameCounts(need, have)) return true; // the very first window for (let right = s1.length; right < s2.length; right++) { have[idx(s2[right])]++; // a letter enters on the right have[idx(s2[right - s1.length])]--; // a letter leaves on the left if (sameCounts(need, have)) return true; // the window after sliding } return false; // no window matched}function sameCounts(a, b) { return a.every((value, i) => value === b[i]);}Try repeated letters (s1 = "adc", s2 = "dcda"): the first window "dcd"
has one d too many, so it fails. One slide later, the window "cda" matches, even
though the d it uses is the second d in s2, not the first. And s1 longer,
which stops on the very first line.
Comparing all 26 counts after every slide is fine (26 is a constant), but we can
skip even that. Keep a number matches: how many of the 26 letters currently
have equal counts in need and have. When a count changes, only that one
letter’s “equal or not” can flip, so matches goes up or down by at most 1. The
window is a permutation exactly when matches === 26.
Matches counter
function checkInclusion(s1, s2) { if (s1.length > s2.length) return false; const need = new Array(26).fill(0); const have = new Array(26).fill(0); const idx = (ch) => ch.charCodeAt(0) - 97; for (let i = 0; i < s1.length; i++) { need[idx(s1[i])]++; have[idx(s2[i])]++; } let matches = 0; // how many of the 26 letters have equal counts for (let c = 0; c < 26; c++) if (need[c] === have[c]) matches++; for (let right = s1.length; right < s2.length; right++) { if (matches === 26) return true; const enter = idx(s2[right]); have[enter]++; if (have[enter] === need[enter]) matches++; // just became equal else if (have[enter] === need[enter] + 1) matches--; // was equal, not any more const leave = idx(s2[right - s1.length]); have[leave]--; if (have[leave] === need[leave]) matches++; else if (have[leave] === need[leave] - 1) matches--; } return matches === 26;}def check_inclusion(s1, s2): if len(s1) > len(s2): return False need, have = [0] * 26, [0] * 26 for i in range(len(s1)): need[ord(s1[i]) - ord("a")] += 1 have[ord(s2[i]) - ord("a")] += 1 matches = sum(1 for c in range(26) if need[c] == have[c]) for right in range(len(s1), len(s2)): if matches == 26: return True enter = ord(s2[right]) - ord("a") have[enter] += 1 if have[enter] == need[enter]: matches += 1 # just became equal elif have[enter] == need[enter] + 1: matches -= 1 # was equal, not any more leave = ord(s2[right - len(s1)]) - ord("a") have[leave] -= 1 if have[leave] == need[leave]: matches += 1 elif have[leave] == need[leave] - 1: matches -= 1 return matches == 26The two ifs after each change are the subtle part. After have[enter]++: if the
count now equals need, it just became a match (matches + 1); if it’s now
exactly one more than need, it was a match a moment ago and isn’t any more
(matches − 1). Leaving works the same way in reverse.
Slide a fixed window, compare counts
function checkInclusion(s1, s2) { if (s1.length > s2.length) return false; const need = new Array(26).fill(0); // letter counts of s1 const have = new Array(26).fill(0); // letter counts of the window const idx = (ch) => ch.charCodeAt(0) - 97; // 'a' -> 0, 'b' -> 1, ... 'z' -> 25 for (let i = 0; i < s1.length; i++) { need[idx(s1[i])]++; have[idx(s2[i])]++; } if (sameCounts(need, have)) return true; // the very first window for (let right = s1.length; right < s2.length; right++) { have[idx(s2[right])]++; // a letter enters on the right have[idx(s2[right - s1.length])]--; // a letter leaves on the left if (sameCounts(need, have)) return true; // the window after sliding } return false; // no window matched}function sameCounts(a, b) { return a.every((value, i) => value === b[i]);}def check_inclusion(s1, s2): if len(s1) > len(s2): return False need = [0] * 26 # letter counts of s1 have = [0] * 26 # letter counts of the window for i in range(len(s1)): need[ord(s1[i]) - ord("a")] += 1 have[ord(s2[i]) - ord("a")] += 1 if need == have: # the very first window return True for right in range(len(s1), len(s2)): have[ord(s2[right]) - ord("a")] += 1 # a letter enters on the right have[ord(s2[right - len(s1)]) - ord("a")] -= 1 # a letter leaves on the left if need == have: # the window after sliding return True return False # no window matchedOn LeetCode it’s var checkInclusion = function(s1, s2) in JavaScript, and
def checkInclusion(self, s1, s2) inside class Solution in Python.
- Line 2 (JS) / lines 2–3 (Python): a window of
len(s1)letters can’t fit inside a shorters2. - Lines 3–4 (JS) / lines 4–5 (Python): two lists of 26 zeros, one slot per letter. A plain list works as a hash map here, because the keys are just the numbers 0 to 25.
- Line 5 (JS):
idxturns a letter into its slot. Every character has a number code;'a'is 97,'b'is 98, socode − 97gives 0 for a, 1 for b, … 25 for z. Python does the same inline withord(ch) - ord("a"). - Lines 6–9 (JS) / lines 6–8 (Python): count
s1intoneed, and the firstlen(s1)letters ofs2(the first window) intohave. - Line 10 (JS) / lines 9–10 (Python): the first window might already match.
- Line 11:
rightis the index of the letter entering the window. It starts right after the first window. - Line 12: the entering letter’s count goes up.
- Line 13: the letter
len(s1)places behindrightleaves, so its count goes down. Now the window holds exactlylen(s1)letters again. - Line 14 (JS) / lines 14–15 (Python): compare.
sameCountschecks the 26 pairs one by one (JS); Python’s==on two lists does the same. - Line 16: no window matched.
s1 = "ab", s2 = "eidbaooo". need is a: 1, b: 1.
| window (indexes) | window | enters | leaves | have (non-zero) | equal? |
|---|---|---|---|---|---|
| 0–1 | ei | — | — | e:1 i:1 | no |
| 1–2 | id | d | e | d:1 i:1 | no |
| 2–3 | db | b | i | b:1 d:1 | no |
| 3–4 | ba | a | d | a:1 b:1 | yes → true |
Each row changes exactly two counts. That’s the whole saving: we never recount the letters in the middle of the window.
Sort every window
Time
O(n · m log m)
About n windows, each sorted from scratch in m log m steps (m = len(s1), n = len(s2)).
Space
O(m)
A sorted copy of the current window.
Fixed window with counts
Time
O(n)
Building the counts takes m steps; each of the n − m slides changes 2 counts and compares 26. 26 is a fixed number, so the work grows in step with n (m is at most n).
Space
O(1)
Two lists of 26 counts, no matter how long the strings are.
With the matches counter the compare drops from 26 steps to 1, but it’s still O(n). Use it when the interviewer asks “can you avoid comparing all 26 counts?”.
What to say out loud:
- “A permutation has the same letter counts, so I’m looking for a window of
len(s1)letters ins2with the same counts.” - “Sorting every window works but costs O(n · m log m).”
- “With a fixed-size sliding window, each slide changes only two counts: O(n) time, O(1) space with 26-slot arrays.”
- Offer the
matchescounter as the follow-up improvement.
Likely follow-up questions:
- “Return every starting index instead of true/false?” That’s Find All Anagrams
in a String (LeetCode #438): the same loop, but collect
right − len(s1) + 1each time the counts match instead of returning. - “What if the strings could contain any character?” Use a hash map instead of a 26-slot array.
Related problems:
- Valid Anagram (week 1): comparing letter counts of two whole strings.
- Longest Repeating Character Replacement: window counts with a window that grows and shrinks.
- The fixed-size sliding window pattern in the week overview.