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.

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 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;
}

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.

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.