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

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.

class Solution:
    def checkInclusion(self, 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.

class Solution:
    def checkInclusion(self, 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):

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.

class Solution:
    def checkInclusion(self, 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 with a genuinely constant (not 26×) cost per slide — the classic final form of the fixed-window pattern.

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).