Generated by Codex with GPT-5

Quick facts

Problem gist

Given two strings s1 and s2, the task is to decide whether s2 contains any contiguous substring that is a permutation of s1.

That means order inside the matching substring does not matter, but the character counts must match exactly. If s1 = "ab", then "ab" and "ba" are both valid windows. If s2 contains either one as a length-2 substring, the answer is True.

The key observation is that every valid candidate in s2 must have length len(s1). The problem is therefore not asking for an arbitrary subsequence or a scattered set of characters. It is asking whether any fixed-size window has the same character-count table as s1.

Core idea

Use a sliding window of length len(s1) over s2.

Build a character balance array from s1. For each letter, the balance starts as “how many of this letter the window still needs.” When a character enters the window, decrement its balance. When a character leaves the window, increment its balance back.

A window is a permutation exactly when every balance value is zero:

  • zero means the window has exactly the required count of that letter
  • positive means the window is missing that letter
  • negative means the window has too many of that letter

Instead of comparing two count arrays at every step, track how many balance entries are nonzero. When that count becomes zero, the current window matches s1.

Deriving the algorithm

First handle the impossible case: if s1 is longer than s2, no substring in s2 can contain a permutation of s1.

Then initialize a 26-element balance array because the problem uses lowercase English letters. Add every character from s1 to the balance. At this point, each positive count represents a needed character.

Now scan s2 from left to right:

  1. Add the new rightmost character to the window by decrementing its balance.
  2. If the window has grown past len(s1), remove the leftmost character by incrementing its balance.
  3. Once the window has reached size len(s1), check whether all balances are zero through the maintained nonzero-entry counter.

The subtle part is maintaining that counter. Whenever a balance changes from zero to nonzero, the counter increases. Whenever a balance changes from nonzero to zero, it decreases. Other changes do not affect it.

Python solution

ALPHABET_SIZE = 26
ASCII_LOWERCASE_A = ord("a")


def _letter_index(character: str) -> int:
    """Map a lowercase English letter to an array index from 0 to 25."""
    return ord(character) - ASCII_LOWERCASE_A


def _apply_balance_delta(
    balance: list[int],
    non_zero_entries: int,
    character: str,
    delta: int,
) -> int:
    """Apply a count change and return the updated nonzero-balance count."""
    index = _letter_index(character)
    before = balance[index]
    after = before + delta

    if before == 0 and after != 0:
        non_zero_entries += 1
    elif before != 0 and after == 0:
        non_zero_entries -= 1

    balance[index] = after
    return non_zero_entries


class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        pattern_length = len(s1)
        text_length = len(s2)

        if pattern_length > text_length:
            return False

        if pattern_length == 0:
            return True

        balance = [0] * ALPHABET_SIZE
        non_zero_entries = 0

        for character in s1:
            non_zero_entries = _apply_balance_delta(
                balance,
                non_zero_entries,
                character,
                1,
            )

        for right_index, entering_character in enumerate(s2):
            # Entering a character satisfies one needed copy, or creates an extra.
            non_zero_entries = _apply_balance_delta(
                balance,
                non_zero_entries,
                entering_character,
                -1,
            )

            if right_index >= pattern_length:
                leaving_character = s2[right_index - pattern_length]
                # Removing a character makes that copy needed again.
                non_zero_entries = _apply_balance_delta(
                    balance,
                    non_zero_entries,
                    leaving_character,
                    1,
                )

            if right_index >= pattern_length - 1 and non_zero_entries == 0:
                return True

        return False

Complexity

Let n = len(s2) and m = len(s1).

Building the initial balance takes O(m) time, and scanning s2 takes O(n) time. Each character update is O(1), so the total time is O(m + n).

The extra space is O(1), because the balance array always has 26 entries regardless of input size.

Interview follow-ups

What if the strings could contain arbitrary Unicode characters?

The fixed 26-element array would no longer be enough. Use a hash map from character to balance instead. The same sliding-window idea still works: increment counts for s1, decrement counts when characters enter the window, and increment counts when they leave.

To keep the check efficient, continue tracking how many characters have nonzero balances. A character whose balance returns to zero can be removed from the map or left with a zero value, as long as the nonzero counter is updated correctly. The time stays O(m + n) on average, while space becomes O(k), where k is the number of distinct characters in s1 plus the current window.

Could this be solved by sorting each window?

Yes, but it is slower. For every length-m window in s2, sort the window and compare it to sorted s1. That works because two strings are permutations when their sorted forms are equal.

The cost is the tradeoff. There are about n - m + 1 windows, and sorting each window costs O(m log m), so the total time becomes O((n - m + 1) * m log m). It is easy to explain but not optimal. The sliding-window count approach avoids redoing almost all of the work between adjacent windows.

What if the interviewer asks for all matching start indices?

Do not return immediately when a matching window is found. Instead, append right_index - pattern_length + 1 to an answer list whenever the nonzero-balance counter reaches zero after the window is full.

The derivation is unchanged because each match still corresponds to a window whose character counts exactly equal s1. The runtime remains O(m + n), and the extra output space is O(r), where r is the number of matching windows.

How would this relate to finding an anagram pattern in a string?

It is the same core problem. “A permutation of s1” and “an anagram of s1” both mean the same multiset of characters in any order. The only difference is usually the required output: this problem asks for a boolean, while an anagram-search variant often asks for all start indices.

The same balance array and sliding window solve both. For the boolean version, return after the first match. For the index-list version, collect every matching left boundary.

Why is a fixed-size window valid here?

Any permutation of s1 must use every character in s1 exactly once, so it must have length len(s1). A shorter window is missing characters, and a longer window has extra characters.

That length constraint is what makes the sliding window clean. The algorithm never needs to decide when to expand or shrink based on content. It always keeps exactly the only possible candidate length, then checks whether the counts match.