Permutation in String: Fixed Window Frequency Matching

"Permutation in String" is a Medium-level staple in Microsoft, Google, Oracle loops, and it is a textbook fit for the Sliding Window pattern — one of the nine patterns that cover the bulk of what FAANG coding interviews actually test. Part 5 of 11 in the Sliding Window arc.

The Problem

Given strings s1 and s2, return True if s2 contains a permutation of s1 as a contiguous substring. Equivalently: does any window of s2 of length len(s1) have exactly the character counts of s1?

Input:  s1 = "ab", s2 = "eidbaooo"
Output: True
The window "ba" is a permutation of "ab".

Recognizing the Sliding Window Pattern

Sliding window maintains a contiguous range over an array or string and slides its boundaries instead of recomputing from scratch. Fixed-size windows update a running aggregate in O(1) per step; variable-size windows grow the right edge and shrink the left only when a constraint breaks. Any problem asking about the best contiguous subarray or substring under a constraint should trigger this pattern.

A permutation constraint is a frequency-vector constraint, and the window size is fixed at len(s1) — so this is the fixed-size template where the aggregate is a character histogram instead of a sum.

The Approach

Build the target histogram and the first window's histogram over the 26 letters. Track matches — how many of the 26 counts agree. Each slide touches two letters, updating matches in O(1) per letter, so a full-histogram comparison never happens inside the loop.

The simpler compare-dicts-each-slide version is O(26·n) and still linear — offer the match-counter as the polish, and mention Python's Counter equality as the pragmatic baseline.

Python Solution

def check_inclusion(s1: str, s2: str) -> bool:
    """True if some window of s2 is a permutation of s1."""
    n, m = len(s1), len(s2)
    if n > m:
        return False

    A = ord("a")
    need = [0] * 26
    have = [0] * 26
    for i in range(n):
        need[ord(s1[i]) - A] += 1
        have[ord(s2[i]) - A] += 1

    matches = sum(1 for i in range(26) if need[i] == have[i])
    if matches == 26:
        return True

    for right in range(n, m):
        for idx, delta in ((ord(s2[right]) - A, 1), (ord(s2[right - n]) - A, -1)):
            if have[idx] == need[idx]:
                matches -= 1          # this letter was matched, will change
            have[idx] += delta
            if have[idx] == need[idx]:
                matches += 1
        if matches == 26:
            return True
    return False

Complexity

• Time: O(n + m) — constant work per slide via the match counter
• Space: O(1) — two 26-slot histograms and a counter

Interview Tips and Follow-Ups

• Guard len(s1) > len(s2) first — skipping it crashes the seed loop and interviewers seed exactly that case.
• Find All Anagrams (next in this arc) is this problem returning every matching start index instead of a boolean.
• If asked about Unicode, switch histograms to dicts and compare sizes lazily — say how the complexity changes.

More Sliding Window problems — and the other eight patterns — live in the Technical Interview category. Drill the pattern, not the problem: that is the entire thesis of this series.