Skip to content
16-Week DSA Roadmap
LeetCode #567MediumProblem 8 of 8

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

The problem in plain English

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".

s2
  1. e0
  2. i1
  3. d2
  4. b3
  5. a4
  6. o5
  7. o6
  8. o7
'ba' (indexes 3 and 4) is a rearrangement of 'ab', so the answer is true.

The rules that matter:

  • The matching block in s2 must have exactly len(s1) letters, all next to each other.
  • Only lowercase a to z.
  • If s1 is longer than s2, the answer is false.

Before you code: think it through

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?”

letter counts (letters not shown are 0 in both)
ab
need (s1)11
have (window)11
Counts of s1 = 'ab' (top row) against the window 'ba' (bottom row). Every column matches, so 'ba' is a permutation of 'ab'.

Pause and think

The window over s2 = 'eidbaooo' is 'db' (indexes 2 and 3). We slide it one step right. Which letter leaves, which enters, and what's the new window?

Approach 1: Sort every window

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"

s2
  1. e0
  2. i1
  3. d2
  4. b3
  5. a4
  6. o5
  7. o6
  8. o7
variables
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".

Step 1 / 5

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 False

Why is it slow?

Let 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.

The pattern: fixed-size sliding 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

Template

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”

Approach 2: Slide a fixed window, compare counts

  1. If s1 is longer than s2, return false.
  2. Make two lists of 26 counts (one slot per letter a–z): need for s1 and have for the first len(s1) letters of s2.
  3. If need equals have, return true.
  4. 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.
  5. After each slide, compare again. If they’re equal, return true.
  6. 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"

s1
  1. a0
  2. b1
s2
  1. e0
  2. i1
  3. d2
  4. b3
  5. a4
  6. o5
  7. o6
  8. o7
letter counts (letters not shown are 0 in both)
need (s1)
have (window)
variables
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").

Step 1 / 12

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.

Optimisation: a matches counter

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 == 26

The 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.

The code, line by line

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 matched

On 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 shorter s2.
  • 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): idx turns a letter into its slot. Every character has a number code; 'a' is 97, 'b' is 98, so code − 97 gives 0 for a, 1 for b, … 25 for z. Python does the same inline with ord(ch) - ord("a").
  • Lines 6–9 (JS) / lines 6–8 (Python): count s1 into need, and the first len(s1) letters of s2 (the first window) into have.
  • Line 10 (JS) / lines 9–10 (Python): the first window might already match.
  • Line 11: right is 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 behind right leaves, so its count goes down. Now the window holds exactly len(s1) letters again.
  • Line 14 (JS) / lines 14–15 (Python): compare. sameCounts checks the 26 pairs one by one (JS); Python’s == on two lists does the same.
  • Line 16: no window matched.

Dry run

s1 = "ab", s2 = "eidbaooo". need is a: 1, b: 1.

window (indexes)windowentersleaveshave (non-zero)equal?
0–1ei——e:1 i:1no
1–2idded:1 i:1no
2–3dbbib:1 d:1no
3–4baada:1 b:1yes → true
s1 = "ab", s2 = "eidbaooo"

Each row changes exactly two counts. That’s the whole saving: we never recount the letters in the middle of the window.

Complexity

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?”.

Common mistakes and edge cases

What to say out loud:

  1. “A permutation has the same letter counts, so I’m looking for a window of len(s1) letters in s2 with the same counts.”
  2. “Sorting every window works but costs O(n · m log m).”
  3. “With a fixed-size sliding window, each slide changes only two counts: O(n) time, O(1) space with 26-slot arrays.”
  4. Offer the matches counter 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) + 1 each 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: