Generated by Codex with GPT 5.6 Sol XHigh

Quick facts

Problem gist

Given a text string s and a shorter pattern string p, the task is to return every starting index in s where a substring is an anagram of p. An anagram may arrange the letters differently, but it must contain exactly the same characters with exactly the same frequencies. Overlapping matches count separately.

The key observation is that every candidate substring has the same length as p. There is no need to consider shorter or longer ranges, so the problem becomes a left-to-right scan of fixed-size windows.

Deriving the optimal solution

A direct solution could sort every window and compare it with a sorted copy of the pattern. That repeats expensive work: neighboring windows share all but two characters. Frequency counts preserve exactly the information that an anagram needs while allowing the window to be updated incrementally.

For each lowercase letter, store this difference:

count in the current window - count in the pattern

If all 26 differences are zero, the window and pattern contain the same multiset of letters, so the window is an anagram. When the window moves one position, only two differences change: the departing character is subtracted and the arriving character is added.

The implementation also tracks how many letter buckets currently have a nonzero difference. Updating a bucket changes this total only when the bucket moves away from zero or returns to zero. A window matches precisely when the total is zero. This avoids rescanning even the 26-element frequency array after each move and makes the same idea efficient if the alphabet is later generalized.

For example, with s = "cbaebabacd" and p = "abc", the first window is "cba". Its three letter counts equal the pattern counts, so index 0 is recorded. Sliding forward updates the count for only the character leaving and the character entering. The next zero-difference window is "bac", beginning at index 6.

Why the sliding window is correct

Before any window is checked, the difference array is built from the pattern and the first len(p) characters of the text. It therefore represents the exact frequency difference between that window and the pattern.

Each slide removes the old leftmost character from the window and adds the new rightmost character. Applying those same two changes to the difference array preserves the invariant for the new window. The mismatch total is kept consistent with every changed bucket, so it is zero if and only if every character frequency is equal. Equal frequencies in two equal-length strings are exactly the definition of an anagram. Consequently, the algorithm records every valid starting index and no invalid one.

If n is the text length and m is the pattern length, initialization and scanning take O(n + m) time. The 26-element difference array uses O(1) auxiliary space for the fixed lowercase-English alphabet. The returned indices require O(k) output space for k matches.

Python solution

from __future__ import annotations


class AnagramWindowFinder:
    """Locate fixed-size windows with the same letter counts as a pattern."""

    ALPHABET_SIZE = 26
    FIRST_LOWERCASE_CODE_POINT = ord("a")

    @classmethod
    def find_start_indices(cls, text: str, pattern: str) -> list[int]:
        """Return the starting index of every pattern anagram in text.

        The LeetCode problem defines both inputs as lowercase English strings.
        Empty patterns are treated as having no matches because the original
        problem requires a nonempty pattern.
        """
        window_size = len(pattern)
        if window_size == 0 or window_size > len(text):
            return []

        # Each bucket stores: current-window count minus pattern count.
        count_differences = [0] * cls.ALPHABET_SIZE

        for character in pattern:
            letter_index = cls._letter_index(character)
            count_differences[letter_index] -= 1

        for character in text[:window_size]:
            letter_index = cls._letter_index(character)
            count_differences[letter_index] += 1

        mismatched_bucket_count = sum(
            difference != 0 for difference in count_differences
        )
        matching_start_indices: list[int] = []

        if mismatched_bucket_count == 0:
            matching_start_indices.append(0)

        for incoming_index in range(window_size, len(text)):
            outgoing_index = incoming_index - window_size
            outgoing_letter = cls._letter_index(text[outgoing_index])
            incoming_letter = cls._letter_index(text[incoming_index])

            mismatched_bucket_count = cls._apply_count_change(
                count_differences,
                outgoing_letter,
                -1,
                mismatched_bucket_count,
            )
            mismatched_bucket_count = cls._apply_count_change(
                count_differences,
                incoming_letter,
                1,
                mismatched_bucket_count,
            )

            if mismatched_bucket_count == 0:
                matching_start_indices.append(outgoing_index + 1)

        return matching_start_indices

    @classmethod
    def _letter_index(cls, character: str) -> int:
        """Map a lowercase English letter to its frequency-array index."""
        letter_index = ord(character) - cls.FIRST_LOWERCASE_CODE_POINT
        if not 0 <= letter_index < cls.ALPHABET_SIZE:
            raise ValueError("text and pattern must contain only a-z")
        return letter_index

    @staticmethod
    def _apply_count_change(
        count_differences: list[int],
        letter_index: int,
        delta: int,
        mismatched_bucket_count: int,
    ) -> int:
        """Update one bucket and return the new number of nonzero buckets."""
        previous_difference = count_differences[letter_index]
        updated_difference = previous_difference + delta
        count_differences[letter_index] = updated_difference

        if previous_difference == 0 and updated_difference != 0:
            return mismatched_bucket_count + 1
        if previous_difference != 0 and updated_difference == 0:
            return mismatched_bucket_count - 1
        return mismatched_bucket_count


class Solution:
    """LeetCode-compatible entry point."""

    def findAnagrams(self, s: str, p: str) -> list[int]:
        return AnagramWindowFinder.find_start_indices(s, p)

Interview follow-ups

What changes if the strings can contain arbitrary characters?

Replace the fixed 26-element array with a hash map keyed by character. The map can still store window counts minus pattern counts, and a separate nonzero-key count can still identify a match in constant expected time per update. Delete keys when their difference returns to zero so the map does not retain irrelevant characters.

The scan remains O(n + m) expected time, but auxiliary space becomes O(u), where u is the number of distinct characters seen in the pattern and active window. Hashing also has a larger constant factor than array indexing. For Unicode text, the interviewer should clarify whether a “character” means a code point or a user-perceived grapheme cluster and whether normalization is required.

What if only the existence of an anagram is needed?

Use the same window invariant, but return True as soon as the mismatch count reaches zero and return False after the final window. Correctness is unchanged because the first zero-difference window is already a complete witness.

Worst-case time remains O(n + m), while a positive case may stop much earlier. Output storage falls from O(k) to O(1) because no list of indices is accumulated.

How can this work when the text arrives as a stream?

Build the pattern differences first, then read characters one at a time. A queue holding at most m characters identifies which character must leave when the next one arrives. After the first m characters, every update can emit the current start index whenever the mismatch count is zero.

The processing cost is O(1) per arriving character for a fixed alphabet. The stream version uses O(m) space for the queue plus the frequency state; unlike the in-memory solution, it cannot retrieve the outgoing character by indexing the original text. If the upstream system can replay the character from m positions earlier, even that queue can be omitted.

What if many patterns must be searched in the same text?

Group patterns by length, since patterns of the same length examine the same sequence of windows. Convert each pattern’s frequency vector into a hashable signature and map that signature to the interested patterns. During one sliding-window pass for that length, look up each window signature and report any matches.

This shares work well when many patterns have relatively few distinct lengths. The cost is roughly one pass over the text per distinct pattern length, plus signature-management overhead. If nearly every pattern has a different length, repeated sliding windows may still be expensive, and there is no direct Aho-Corasick shortcut because anagrams ignore character order.

How does the approach change for the minimum window containing all pattern characters?

That is a variable-size-window problem rather than a fixed-size-window problem. Expand the right edge until the window satisfies every required count, then move the left edge inward while the requirement stays satisfied. Record the shortest valid interval encountered and repeat.

Each edge moves only forward, so the solution is still O(n + m) time. The important correctness condition changes: an anagram requires every count to be exactly equal, while a containing window allows surplus characters and needs only every required count to be met.

Can the scan be parallelized for a very large text?

Split the text into chunks, but give each chunk an overlap of m - 1 characters on its right. That overlap ensures a worker can evaluate every length-m window that begins in its assigned non-overlapping region, including windows that cross the physical boundary. Each worker runs the same sliding-window algorithm and returns only starts owned by its region.

The total computational work stays linear apart from boundary overlap, and results can be merged in chunk order. Parallelism is worthwhile only when the text is large enough to offset worker startup, duplicated overlap work, and result coordination; a single linear scan is usually faster for ordinary interview-sized inputs.