Sliding Window · LC #567

Permutation in String

Fixed-size sliding window over s2 of length len(s1); compare character frequency maps to detect any anagram of s1. A balanced count array avoids O(26) equality checks.

mediumLC #567AMZ★★GOO★META★★MSFT★★AAPL★

Mark as done

Confidence

Ask GPT Practice on LeetCodePractice

Statement

Problem & Approach

Problem statement, sample I/O, and key reasoning.

Given strings `s1` and `s2`, return `true` if `s2` contains a permutation of `s1` (i.e., any anagram of `s1` appears as a substring of `s2`).

Sample I/O

Input:  s1 = "ab", s2 = "eidbaooo"
Output: true   ("ba" is a substring)

Input:  s1 = "ab", s2 = "eidboaoo"
Output: false

Time: O(|s1|+|s2|) · Space: O(1)

Intuition

How to Think About It

Intuition

Two strings are permutations of each other iff their character frequency maps are identical. Instead of recomputing the map for every window, maintain a difference counter: initialise it from s1, then subtract s2 characters as you enter the window and add them back as they leave. When the difference counter is all-zero, the window is a permutation.

Core Concept

Build count[] from s1 (increment). For the first len(s1) chars of s2, decrement count[]. Check allZero. Then slide: decrement for incoming s2[i], increment for outgoing s2[i - len(s1)]. Check allZero each step. Time O(n + m) where n=len(s1), m=len(s2). Space O(1) (26-char alphabet).

When to use

Any "does s2 contain an anagram/permutation of s1" style problem. Also the building block for Find All Anagrams in a String (LC 438).

When NOT to use

When you need all positions (return list) - solve a slight variant. When s1 is longer than s2 (early return false). When the alphabet is large (use HashMap instead of array).

Key Insights

What to Know Cold

Two strings are anagrams iff their sorted forms are equal - equivalently, their frequency maps are identical.
The balance array trick (count from s1, subtract s2) avoids a full map comparison on every window slide.
Tracking a `matches` counter (26 initially, decremented when count[i] reaches 0) reduces the allZero check to O(1).
The window is exactly fixed at len(s1) - use the simpler fixed-window structure rather than variable-window.
Out-going character restoration: when a character leaves the window, its count increments back; if it was 0 (matched), it now unmatches.

1 example

Worked Examples

Fixed window anagram check - Python

Check if "eidbaooo" contains any permutation of "ab".

Counter of s1; slide window of len(s1) over s2; compare Counters.

from collections import Counter
def checkInclusion(s1: str, s2: str) -> bool:
    if len(s1) > len(s2): return False
    c1 = Counter(s1)
    window = Counter(s2[:len(s1)])
    if c1 == window: return True
    for i in range(len(s1), len(s2)):
        window[s2[i]] += 1
        out = s2[i - len(s1)]
        window[out] -= 1
        if window[out] == 0: del window[out]
        if c1 == window: return True
    return False
# "ab","eidbaooo" → True

Output: True

Pattern directly generalises to Find All Anagrams and Minimum Window; fixed-window frequency-map comparison is a very common interview building block.