Permutation in String

mediumTests passed 2026-11-11v1.0.0

TC: O(N)|SC: O(1)

Sliding Window Original Statement (leetcode).md

1. Core Invariant / The Trick

Maintain a fixed window of size `len(s1)` sliding over `s2`, updating character match count `matches` out of 26 in O(1) per slide instead of comparing two 26-arrays every step.

2. Complexity Bounds & Proof

Pre-computes initial window, then performs O(1) incremental adjustment for incoming and outgoing char.

3. Minimal Idiomatic Code

def checkInclusion(s1: str, s2: str) -> bool:
    if len(s1) > len(s2): return False
    c1, c2 = [0] * 26, [0] * 26
    for i in range(len(s1)):
        c1[ord(s1[i]) - 97] += 1
        c2[ord(s2[i]) - 97] += 1
    matches = sum(1 for i in range(26) if c1[i] == c2[i])
    for r in range(len(s1), len(s2)):
        if matches == 26: return True
        idx_in = ord(s2[r]) - 97
        c2[idx_in] += 1
        if c2[idx_in] == c1[idx_in]: matches += 1
        elif c2[idx_in] - 1 == c1[idx_in]: matches -= 1
        idx_out = ord(s2[r - len(s1)]) - 97
        c2[idx_out] -= 1
        if c2[idx_out] == c1[idx_out]: matches += 1
        elif c2[idx_out] + 1 == c1[idx_out]: matches -= 1
    return matches == 26

4. Failure Modes & Interview Follow-ups

Pitfalls:- Guarding `len(s1) > len(s2)` immediately prevents index bounds errors.

Follow-ups:- Find All Anagrams in a String records every index where `matches == 26`.

Personal Notes & Scratchpad (Local-First Yjs CRDT)

Saved instantaneously in IndexedDB. Streams live across peers via Hocuspocus when signed in.

Related Invariants

Valid Anagram (O(N))

Browser Scratchpad

Console Output

Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.