Permutation in String

Problem

You are given two strings s1 and s2. Decide whether s2 contains any permutation of s1 as a contiguous substring — in other words, whether some window of s2 uses exactly the same characters as s1, with exactly the same multiplicities, in any order. Return True if such a window exists, otherwise False.

Examples

s1 = "ab", s2 = "eidbaooo" → True — the window "ba" (indices 3–4) is a rearrangement of "ab".
s1 = "ab", s2 = "eidboaoo" → False — no two adjacent characters of s2 are exactly {a, b}.
s1 = "adc", s2 = "dcda" → True — the window "cda" (indices 1–3) is a permutation of "adc".

Constraints

1 <= len(s1), len(s2) <= 10^4
Both strings consist of lowercase English letters only.
The 10^4 bound rules out re-scanning each window from scratch; an O(n) or O(26·n) pass is expected.

Think about it first

Hint 1

Two strings are permutations of each other exactly when they have identical character counts. You never need to generate actual permutations.

Hint 2

Every candidate substring has exactly `len(s1)` characters. That means the window size is fixed — you are sliding a window of constant width across `s2`.

Hint 3

Keep a count array for the current window. When the window slides one step, only two characters change: one enters on the right, one leaves on the left. Update the counts (or a running "how many of the 26 letters match" tally) in O(1) and check for a full match.

TL;DR

Fixed-size sliding window with a running “matched letters” counter — O(n) time, O(1) space (two 26-slot arrays).

Approach 1 — Brute force (sort every window)

A permutation of s1 becomes literally equal to s1 once both are sorted. So sort s1 once, then sort every length-m window of s2 and compare.

def checkInclusion(s1: str, s2: str) -> bool:
    m, n = len(s1), len(s2)
    if m > n:
        return False
    target = sorted(s1)
    for i in range(n - m + 1):
        window = s2[i:i + m]
        if sorted(window) == target:
            return True
    return False

Complexity: O((n − m + 1) · m log m) time, O(m) space.

With n = m = 10^4 this is on the order of 10^8+ character operations — the constraints are chosen to make re-processing each window from scratch too slow.

Approach 2 — Fixed window, compare count arrays

The insight: “is a permutation of s1” ⇔ “has the same 26-letter histogram as s1”. Maintain the histogram of the current window incrementally: when the window slides, one character enters and one leaves, so the histogram changes in O(1). Comparing two 26-element arrays is O(26), a constant.

def checkInclusion(s1: str, s2: str) -> bool:
    m, n = len(s1), len(s2)
    if m > n:
        return False

    need = [0] * 26
    window = [0] * 26
    for i in range(m):
        need[ord(s1[i]) - 97] += 1
        window[ord(s2[i]) - 97] += 1

    if window == need:
        return True

    for right in range(m, n):
        window[ord(s2[right]) - 97] += 1        # enters
        window[ord(s2[right - m]) - 97] -= 1    # leaves
        if window == need:
            return True
    return False

Walkthrough with s1 = "ab", s2 = "eidbaooo" (m = 2):

window	histogram vs `{a:1, b:1}`	match?
`"ei"`	e:1, i:1	no
`"id"`	i:1, d:1	no
`"db"`	d:1, b:1	no
`"ba"`	b:1, a:1	yes → return True

Complexity: O(26 · n) = O(n) time, O(1) space.

Approach 3 — Sliding window with a `matches` counter

The insight: you don’t need to re-compare all 26 letters after every slide. Keep an integer matches = number of letters whose count agrees between need and window. A slide touches at most two letters, and each touch can change that letter’s agreement status in O(1). The window is a permutation exactly when matches == 26.

def checkInclusion(s1: str, s2: str) -> bool:
    m, n = len(s1), len(s2)
    if m > n:
        return False

    need = [0] * 26
    window = [0] * 26
    for i in range(m):
        need[ord(s1[i]) - 97] += 1
        window[ord(s2[i]) - 97] += 1

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

    for right in range(m, n):
        r = ord(s2[right]) - 97
        if window[r] == need[r]:
            matches -= 1
        window[r] += 1
        if window[r] == need[r]:
            matches += 1

        l = ord(s2[right - m]) - 97
        if window[l] == need[l]:
            matches -= 1
        window[l] -= 1
        if window[l] == need[l]:
            matches += 1

        if matches == 26:
            return True
    return False

Walkthrough with s1 = "ab", s2 = "eidbaooo": the initial window "ei" matches 22 letters (all except a, b, e, i). Sliding to "id": d enters (a match on d breaks: 21), e leaves (e back to 0: 22 → net 22). Sliding to "db": b enters (b now agrees: +1), i leaves (i agrees again: +1) → 24. Sliding to "ba": a enters (+1), d leaves (+1) → 26 → matches == 26, return True.

Complexity: O(n + m) time, O(1) space. Same big-O as Approach 2, but each slide costs a true constant instead of a 26-element comparison.

Common pitfalls

Forgetting the m > n early exit — the initial window build would index past the end of s2.
Checking only after the first slide and never testing the initial window itself.
In the matches version, updating the count before checking whether that letter currently agrees — the decrement/increment of matches must bracket the count change.
Trying to generate permutations of s1 (up to 10^4! of them) instead of comparing histograms.

Pattern takeaway

When the thing you’re searching for has a fixed length, the window size is known in advance: slide a constant-width window and maintain its summary (here, a character histogram) incrementally — one element enters, one leaves, O(1) per step. Comparing summaries can itself be made incremental with a “how many components already agree” counter, turning O(alphabet) per step into O(1).