Sliding Window Pattern

Permutation in String

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise. In other words, return true if one of s1's permutations is a substring of s2. A permutation is a rearrangement of all characters.

CONSTRAINTS

1 <= s1.length, s2.length <= 10^4
s1 and s2 consist of lowercase English letters only

EXAMPLE 1

Input: s1 = "ab", s2 = "eidbaooo"

Output: true

s2 contains "ba" starting at index 3, which is a permutation of "ab". Character frequencies match: a=1, b=1.

EXAMPLE 2

Input: s1 = "ab", s2 = "eidboaoo"

Output: false

No window of size 2 in s2 has both an "a" and a "b" as adjacent characters. No permutation of s1 is a substring.

EXAMPLE 3

Input: s1 = "adc", s2 = "dcda"

Output: true

"dca" at index 1 is a permutation of "adc". Frequencies a=1,c=1,d=1 match in both.

Are the strings case-sensitive?

Yes, but both strings consist only of lowercase English letters (a-z), so no special casing logic is needed.

What if s1 is longer than s2?

A permutation of s1 cannot fit inside a shorter string s2. Return false immediately if s1.length > s2.length.

Do I need to find all positions or just confirm existence?

Just return true or false — confirm that at least one permutation of s1 exists as a contiguous substring in s2.

Does the order of characters in s1 matter?

No — any rearrangement of s1's characters counts. 'ab' and 'ba' are both valid permutations of 'ab'.

A permutation of s1 is just its letters shuffled into some order. So the question "does s2 contain a permutation of s1?" really means: is there some stretch of s2, exactly as long as s1, that uses the very same letters the very same number of times? Order inside that stretch does not matter at all — only which letters and how many of each. That last phrase is the key: two strings are permutations of each other exactly when their letter counts match.

The obvious way, and its cost

Let m = len(s1). Walk every window of length m in s2, and check whether it is a rearrangement of s1. The simplest check is to sort both and compare, or to build a fresh letter-count for the window and compare it to s1's counts.

python

from collections import Counter
def brute_force(s1, s2):
    target = Counter(s1)
    m = len(s1)
    for i in range(len(s2) - m + 1):
        if Counter(s2[i:i+m]) == target:   # rebuilds counts from scratch each time
            return True
    return False

There are about N windows, and each one rebuilds a count over m letters, so this is O(N × m). For strings up to 10⁴ that is far too much repeated work — and it is the same repeated work we already met in Maximum Sum Subarray: neighbouring windows overlap in all but two letters, yet we throw the overlap away and recount it.

Carry the counts instead of rebuilding them

This is the fixed sliding window again — with one twist. In Maximum Sum Subarray the summary of a window was a single number, a running sum. Here the summary is richer: a small tally of how many of each letter the window holds (just 26 slots, one per lowercase letter). Everything else is identical. When the window slides one step, exactly one letter leaves on the left and one enters on the right, so we patch the tally with two updates — drop one from the outgoing letter, add one to the incoming letter — and never recount the middle.

A window is a permutation of s1 precisely when its 26-slot tally equals s1's tally.

python

from collections import Counter
def check_inclusion(s1, s2):
    m = len(s1)
    if m > len(s2): return False
    target = Counter(s1)
    window = Counter(s2[:m])          # build the first window once, in full
    if window == target: return True
    for i in range(m, len(s2)):
        window[s2[i]] += 1            # incoming letter
        window[s2[i - m]] -= 1        # outgoing letter
        if window[s2[i - m]] == 0:
            del window[s2[i - m]]     # keep a bare-zero out so the maps compare equal
        if window == target: return True
    return False

Crucial Notewe delete a letter from the tally the moment its count hits zero. Without that, the window map keeps a stray {'e': 0} that the target map does not have, and the two dicts compare unequal even when the real letters match. (Comparing two 26-slot tallies is O(26) = constant work; if you want to shave even that, track a single "how many letters are already at their target count" number and nudge it as counts change — but the constant-factor version above is already O(N).)

Worked Example:s1 = "ab", s2 = "eidbaooo"
Target tally: {a:1, b:1}. Window width 2.
- First window "ei" → {e:1, i:1}. No match.
- Slide: add d, drop e → "id" {i:1, d:1}. No match.
- Slide: add b, drop i → "db" {d:1, b:1}. No match.
- Slide: add a, drop d → "ba" {b:1, a:1}. Matches the target — return true.

And a near-miss: s1 = "ab", s2 = "eidboaoo". The windows are "ei", "id", "db", "bo", "oa", "ao", "oo" — no window ever holds both an 'a' and a 'b' at once, so every tally misses the target and the answer is false. Sharing the letters is not enough; they have to sit inside one window together.

Mapping it onto the pattern

This is the fixed sliding window from Maximum Sum Subarray with only the state swapped. Filling the four slots: (a) width = len(s1); (b) state = a 26-letter tally of the window; (c) fold in/out = +1 on the incoming letter, −1 on the outgoing one; (d) record = "does the tally equal the target's tally?" — stop at the first yes.

The reason the pattern fires here is worth naming, so you catch the next one: any question about anagrams or permutations is secretly a question about letter counts, and counts are exactly the kind of summary you can repair one-in, one-out. Add the words "contiguous / substring" and a fixed length (here, the length of the other string), and the fixed window is the natural fit. If instead the target length were not fixed — "the shortest window of s2 containing all of s1's letters" — the frame would have to stretch, pushing you to the variable window (that is Minimum Window Substring).

Interactive Strategy Visualization