Permutation in String

Permutation in String is the classic fixed-size sliding window. It teaches a move you will reuse constantly: scan a string once, keeping a window of a known length and a running letter count, updating it in O(1) as the window slides.

The slow way first

The obvious idea: look at every substring of s2 that has the same length as s1, sort it (or count its letters), and compare to s1. There are about n such windows and sorting each costs O(k log k), so this is roughly O(n · k log k) — wasteful, because neighboring windows overlap almost entirely.

The question to ask: when the window shifts by one, what actually changed? Only two letters: the one that fell off the left and the one that joined on the right. Everything else is identical, so recomputing the whole window from scratch is pure waste.

The idea: a window that slides

Keep a window of length len(s1) and a count have of its letters. A window is a permutation of s1 exactly when have == need, where need is the letter count of s1. To move the window right by one, do two O(1) updates: add the new right letter and remove the old left letter. Compare and repeat.

The key insight: comparing two small fixed-size letter counts is O(1), and updating the window is O(1), so the whole scan is O(n).

Walk through it

Step through the animation. need = {a:1, b:1}. The window starts on "ei" — no match. It slides to "id", then "db" (a b but no a), then "ba". At "ba" the count is {b:1, a:1}, which equals need, so we return True immediately without scanning the trailing ooo.

Pseudocode

if len(s1) > len(s2): return False
need = letter counts of s1
have = letter counts of the first window s2[0 : len(s1)]
if have == need: return True
for r from len(s1) to len(s2) - 1:
    add s2[r] to have                       # letter entering on the right
    remove s2[r - len(s1)] from have         # letter leaving on the left
    if have == need: return True
return False

The Python solution

def check_inclusion(s1, s2):
    if len(s1) > len(s2):
        return False
    need = Counter(s1)
    have = Counter(s2[:len(s1)])
    if have == need:
        return True
    for r in range(len(s1), len(s2)):
        have[s2[r]] += 1
        have[s2[r - len(s1)]] -= 1
        if have[s2[r - len(s1)]] == 0:
            del have[s2[r - len(s1)]]
        if have == need:
            return True
    return False

• need is the target letter count; have is the count for the current window.
• We seed have from the first window and compare once before sliding (the loop only handles windows 1 onward).
• Lines 9–10 are the heart: add the entering letter s2[r], drop the leaving letter s2[r - len(s1)] — both O(1).
• We del a key once its count hits 0 so that have == need is an exact dictionary equality (a leftover {x: 0} would make them unequal).
• Each have == need check compares at most 26 entries, so it is O(1).

Complexity

Space is O(1): the counts hold at most 26 lowercase letters regardless of input size. We turned an O(n · k log k) scan into a single O(n) pass by updating the window instead of rebuilding it.

When this pattern shows up

Practice