Permutation in String

This question looks like it needs permutations, which grow as n factorial. It does not. A rearrangement of a word is simply any string with the same letter counts, and "a substring of the same length" is a fixed-size window. So this is a fixed window whose summary is a count of each letter.

The problem

Given two strings pattern and text, return True if some rearrangement of pattern appears as a contiguous substring of text.

• pattern = "abc", text = "ecbbacd" → True. The substring "bac" at index 3 uses exactly one a, one b and one c.
• pattern = "ab", text = "acbdb" → False. The length-2 pieces are ac, cb, bd and db; none is ab or ba.

Constraints: 1 ≤ lengths ≤ 10⁴, lowercase English letters only.

Clarifying questions

• Lowercase letters only? Yes. That allows a 26-slot array instead of a dictionary.
• Can pattern be longer than text? Yes; then the answer is False.
• Return a yes/no, or where? Yes/no here. Returning every starting index is the Find All Anagrams follow-up.

Approach 1: sort every window

A piece of text is a rearrangement of pattern exactly when the two sort to the same string. Sort pattern once, then sort every window of the same length and compare.

1def check_inclusion_brute(pattern: str, text: str) -> bool:2    """Sort every window of len(pattern) and compare with the sorted pattern."""3    m = len(pattern)4    target = sorted(pattern)5    for start in range(len(text) - m + 1):6        if sorted(text[start:start + m]) == target:7            return True8    return False

Time: O((n − m + 1) · m log m), where n = len(text) and m = len(pattern). Space: O(m).

With n = 10⁴ and m = 5 × 10³, that is about 5 × 10³ windows, each sorting 5 × 10³ characters: roughly 3 × 10⁸ operations. Generating actual permutations would be far worse: 10 letters already have 3.6 million orderings.

The key insight

Two strings are rearrangements of each other exactly when they have the same count of every letter. Order does not matter, so you never need to sort.

And a window of fixed length m can keep its letter counts up to date in O(1) per slide: one letter enters (count + 1) and one leaves (count − 1). So compute the pattern's counts once, slide a window of length m across text, and after each slide ask "are the counts equal?".

Approach 2: compare 26-letter counts

1def check_inclusion(pattern: str, text: str) -> bool:2    """Fixed window of len(pattern); compare 26-letter count arrays."""3    m = len(pattern)4    if m > len(text):5        return False6    need = [0] * 267    window = [0] * 268    for ch in pattern:9        need[ord(ch) - ord("a")] += 110    for end, ch in enumerate(text):11        window[ord(ch) - ord("a")] += 1               # entering letter12        if end >= m:13            window[ord(text[end - m]) - ord("a")] -= 1  # leaving letter14        if window == need:15            return True16    return False

Until end reaches m − 1 the window is still filling up and holds fewer than m letters, so it cannot equal need. After that it always holds exactly m letters.

Dry run on pattern = "abc", text = "ecbbacd" (need: a 1, b 1, c 1):

Time: O(m + 26·n): each slide is O(1), plus a 26-slot comparison. With a fixed alphabet that is O(n + m). Space: O(1), two arrays of 26.

Approach 3: count matching letters, O(1) per step

The comparison touches all 26 slots every step. Instead, keep one number, matches: how many of the 26 letters currently have the same count in the window as in the pattern. The window is a rearrangement exactly when matches == 26. Each slide changes only two slots, so only those two can change matches.

1def check_inclusion_matches(pattern: str, text: str) -> bool:2    """Track how many of the 26 letters have equal counts: O(1) per step."""3    m = len(pattern)4    if m > len(text):5        return False6    need = [0] * 267    window = [0] * 268    for ch in pattern:9        need[ord(ch) - 97] += 110    matches = sum(1 for i in range(26) if need[i] == window[i])1112    def change(index: int, delta: int) -> None:13        nonlocal matches14        if window[index] == need[index]:15            matches -= 1          # it was equal and is about to change16        window[index] += delta17        if window[index] == need[index]:18            matches += 1          # it is equal now1920    for end, ch in enumerate(text):21        change(ord(ch) - 97, +1)22        if end >= m:23            change(ord(text[end - m]) - 97, -1)24        if matches == 26:25            return True26    return False

On the example, matches starts at 23 (the 23 letters that neither string uses). It moves 22, 23, 24, 24, 24, and reaches 26 when c enters at end = 5. Time: O(n + m). Space: O(1). This is the same idea as the formed counter in Minimum Window Substring.

Edge cases

• Pattern longer than text. Returned as False before any work.
• Pattern equals text in length. Only one window; it is compared once.
• Repeated letters, pattern = "aab". Counts handle multiplicity: a window with one a and two bs has the wrong counts and does not match.
• Using dictionaries instead of arrays. If you use dict counts, delete a key when its count drops to 0; a plain dict treats {"a": 1, "b": 0} and {"a": 1} as different. (Python's Counter ignores zero counts in == since Python 3.10, but it is clearer not to rely on that.)

Follow-ups

• "Return every start index of an anagram." Same window; instead of returning on the first match, append end − m + 1 to a list whenever the counts match (Find All Anagrams in a String).
• "Any Unicode characters." Replace the arrays with dictionaries of counts, and delete keys that reach zero.
• "Allow up to one wrong letter." The window stays fixed; accept when the total difference between counts is at most 2 (one letter too many, one too few). Track that difference instead of matches.