Permutation in String

Check whether one string contains a permutation of another.

Check whether s2 contains any permutation of s1. Since any valid answer has fixed length |s1|, this is a fixed-size window problem rather than a variable-size one.

StringSliding Window

Pattern fit

Because the target length is fixed, this is a clean fixed-size sliding window with exact frequency matching.

Key observation

Any valid window must have the same length as s1, so the problem reduces to whether any length-|s1| window matches the needed character counts.

Target complexity

O(n) / O(1)

How to break down the solution cleanly

Count the characters needed by s1.

Slide a fixed-size window of length s1.length across s2.

Whenever a character enters or leaves the window, update the frequency difference.

If all counts match at any moment, a permutation exists.

Walk through one example

Example: s1 = "ab", s2 = "eidbaooo".

Window "ei" does not match, nor does "id".

When the window becomes "ba", character counts match s1 exactly.

So the answer is true.

Reference implementation

Python

from collections import Counter

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

    need = Counter(s1)
    window = Counter(s2[:window_length])
    if window == need:
        return True

    for right in range(window_length, len(s2)):
        left_char = s2[right - window_length]
        window[left_char] -= 1
        if window[left_char] == 0:
            del window[left_char]

        window[s2[right]] += 1
        if window == need:
            return True

    return False

Common pitfalls

warning

Using variable-size window logic and making the state harder than necessary.

warning

Comparing full maps too often instead of maintaining a match count.

Common follow-ups

How would you generalize this to finding all anagrams?

Why is fixed-size window the natural model here?

Continue with related problems

Build repeatable depth inside the Sliding Window cluster before moving on.

view_weekBack to the pattern page

#76

Minimum Window Substring

Find the smallest substring that contains all characters of t.

Longest Substring Without Repeating Characters

Find the length of the longest substring with no repeated characters.

#424

Longest Repeating Character Replacement

Find the longest substring that can become all one character after at most k replacements.