4.6.4 — Permutation in String

LeetCode 567 · Medium

The problem

Return true if s2 contains any permutation of s1 as a contiguous substring.

s1 = "ab", s2 = "eidbaooo"    →  true    ("ba" is a permutation of "ab")
s1 = "ab", s2 = "eidboaoo"    →  false

Both strings are lowercase English letters.

Constraints:

• 1 \le s1.length, s2.length \le 10,000.

Plain English: You have a small target string and a large main string. Does any scrambled version of the target string appear consecutively anywhere inside the main string?

The pattern

A permutation of s1 is any arrangement of exactly its letters. From 4.4.2 you know that means the same letter counts. And a permutation has the same length as the original.

So the question becomes: is there a window of s2, of length exactly len(s1), whose letter counts match s1's?

This is a fixed-size window, which is simpler than the ones before it. There is no shrink rule and no while loop. The window slides one step at a time: add the character entering on the right, remove the one leaving on the left, and compare.

The ELI5 Analogy: Imagine you're holding a cardboard stencil that is exactly the length of s1, with a cutout. You place this stencil over the start of s2. You count the letters you can see through the hole. If they exactly match the counts of the letters in s1, you win! If not, you slide the stencil exactly one letter to the right. One old letter gets covered up (leaves the window), and one new letter is revealed (enters the window). You never resize the stencil; it's always fixed.

The naive version, and its cost

Rebuild the count for every window and compare. There are n windows, each costs O(m) to build and O(26) to compare, so it is O(n \cdot m).

The waste is obvious once named: two neighbouring windows differ by only two characters. Rebuilding the whole count throws away everything you already knew.

The solution

Python

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        if len(s1) > len(s2):
            return False

        need = [0] * 26
        window = [0] * 26
        for i in range(len(s1)):
            need[ord(s1[i]) - ord('a')] += 1
            window[ord(s2[i]) - ord('a')] += 1     # the first window

        if need == window:
            return True

        for right in range(len(s1), len(s2)):
            window[ord(s2[right]) - ord('a')] += 1                 # entering
            window[ord(s2[right - len(s1)]) - ord('a')] -= 1       # leaving
            if need == window:
                return True

        return False

TypeScript

function checkInclusion(s1: string, s2: string): boolean {
  if (s1.length > s2.length) return false;
  const a = 'a'.charCodeAt(0);

  const need = new Array(26).fill(0);
  const window = new Array(26).fill(0);
  for (let i = 0; i < s1.length; i++) {
    need[s1.charCodeAt(i) - a]++;
    window[s2.charCodeAt(i) - a]++;
  }

  const same = () => need.every((v, i) => v === window[i]);
  if (same()) return true;

  for (let right = s1.length; right < s2.length; right++) {
    window[s2.charCodeAt(right) - a]++;
    window[s2.charCodeAt(right - s1.length) - a]--;
    if (same()) return true;
  }

  return false;
}

Code Walkthrough

• need = [0] * 26, window = [0] * 26: We use arrays of size 26 (since we only have lowercase English letters) to act as frequency maps.
• for i in range(len(s1)):: We set up our initial stencil at the very beginning of s2. We count what we need from s1, and what we currently have in our window.
• if need == window: return True: If the very first window is a match, we're done.
• for right in range(len(s1), len(s2)):: Now we slide the stencil one position at a time. right is the index of the new character entering the window.
• window[ord(...) - ord('a')] += 1: We add the new character on the right to our window count.
• window[... - ord('a')] -= 1: We subtract the old character that just fell out of the left side of the window. Its index is exactly right - len(s1).
• if need == window: return True: Check if the newly updated window matches.

The character leaving the window is at right - len(s1). Getting that index wrong by one is the usual bug. Check it: when right is exactly len(s1), the leaving character is at index 0, which is right — the window has just slid off the first character.

Comparing two 26-slot arrays is O(26), a constant. So the whole thing is O(n).

The O(1)-per-step version

Comparing 26 slots on every step is constant but not free. You can make each step genuinely O(1) by tracking how many of the 26 letters currently match.

matches = sum(1 for i in range(26) if need[i] == window[i])

Then on each slide, only two slots change, so only those two can flip between matching and not matching. Adjust matches for each, and the answer is matches == 26.

The bookkeeping is fiddly: when you increment a slot, it either just became equal (matches goes up) or it just left equality (matches goes down). Write it carefully or not at all. In an interview, the 26-slot comparison is the better answer — it is a constant, it is obviously correct, and offering the refinement afterwards shows you know it exists.

Edge cases

• s1 is longer than s2: Handled by the first if statement. A string can't contain a permutation of something longer than itself.
• Exact match at the end: s1="ab", s2="eidba". The loop reaches the end, updates the window, checks need == window, and returns True just before exiting.
• Multiple identical characters: s1="aab". The array naturally handles counting multiple as.

Complexity

O(n + m) time, O(1) space — 52 integers regardless of input size.

Where this goes next

• Find All Anagrams in a String (LeetCode 438) — the same code, but collect every matching start index instead of returning on the first. Almost identical, and a good self-test.
• Minimum Window Substring — the counts again, but now the window size is not fixed and you want the shortest valid one. That is 4.6.5 and it is considerably harder.

The distinction worth keeping: fixed-size windows have no while loop. If you know the window length up front, you slide; if the length is what you are optimising, you grow and shrink. Deciding which one you are in, before writing anything, saves a lot of confusion.

What the interviewer will push on

"Why is comparing 26 slots still O(1)?" Because 26 is fixed by the constraints. It does not grow with the input.

"Can you make each step O(1) without the 26 comparisons?" The matches counter. Say the idea; you do not have to write it unless asked.

"What if the alphabet were Unicode?" Arrays become maps, and the comparison is no longer constant. The matches counter becomes worth doing rather than optional.

"What if s1 is longer than s2?" The early return. Without it, the first loop reads past the end of s2.

One thing to volunteer: say that this is Valid Anagram run over every window, and that the only new idea is updating the count incrementally instead of rebuilding it.

Next: 4.6.5 Minimum Window Substring — the hardest window problem, where the target is the shortest valid window instead of the longest.