Permutation in String

Signal

A fixed-size window whose target shape (a frequency map) is known in advance — when the window length equals a fixed pattern's length and you're checking "does this window's character count match a required count," that's a fixed-size sliding window with count comparison, not a variable window.

Approach

Precompute the pattern's character frequency. Slide a window of that exact length across the target string, maintaining a running frequency count of the window's contents by adding the entering character and removing the one that just fell out the left side. After each slide, compare the window's count to the pattern's. A match means a permutation of the pattern ends at that position.

Skeleton

need = count(pattern)
window = count(s[0 : len(pattern)])
if window == need: return True
for right in range(len(pattern), len(s)):
    add s[right] to window
    remove s[right - len(pattern)] from window
    if window == need: return True
return False

Solution

from collections import Counter

def check_inclusion(pattern: str, s: str) -> bool:
    k = len(pattern)
    if k > len(s):
        return False
    need = Counter(pattern)
    window = Counter(s[:k])
    if window == need:
        return True
    for right in range(k, len(s)):
        window[s[right]] += 1
        left_char = s[right - k]
        window[left_char] -= 1
        if window[left_char] == 0:
            del window[left_char]
        if window == need:
            return True
    return False

Complexity

O(n · 26) ≈ O(n) time — each slide does O(1) count updates plus an O(26) comparison over the fixed alphabet. O(26) space for the two counters.

Pitfalls

• Comparing full alphabet-sized count tables on every slide is fine here (a constant factor), but the natural follow-up optimization is a single integer "matches" counter that increments/decrements as individual character counts cross into or out of equality with need — mention it if asked to go faster.
• Forgetting to delete zero-count entries when using a Counter — a stray char: 0 entry makes window == need fail even when every visible count matches.
• Off-by-one on the window's trailing edge: the character leaving is s[right - k], not s[right - k - 1].