047. Permutation Inclusion

Why this mechanism works

Every possible answer has length len(pattern). Maintain a fixed window frequency map and compare it with the pattern's frequencies. Deleting zero counts makes dictionary equality reflect true multisets. This intentionally direct version favors a transparent state contract; a mismatch counter can optimize large alphabets later.

State and boundaries

need is the pattern multiset. window is the most recent at-most-m characters, with only positive counts.

Protocol

1. Handle an empty pattern.
2. Add each incoming character.
3. Remove the character more than m positions behind.
4. Compare maps only once a full window exists.
5. Return True on equality, otherwise False at the end.

Visualization

pattern ab -> {a:1,b:1}
text eid[ba]ooo
window ba has the same multiset

Python implementation

from collections import Counter

def permutation_inclusion(pattern, text):
    m = len(pattern)
    if m == 0:
        return True
    need, window = Counter(pattern), {}
    for right, char in enumerate(text):
        window[char] = window.get(char, 0) + 1
        if right >= m:
            old = text[right - m]
            window[old] -= 1
            if window[old] == 0:
                del window[old]
        if right + 1 >= m and window == need:
            return True
    return False

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L4 permutation_inclusion: m = len(pattern)
pattern='ab'; text='eidbaooo'; m=2

L7 permutation_inclusion: need, window = Counter(pattern), {}
pattern='ab'; text='eidbaooo'; m=2; need={'a':1, 'b':1}; window={}

L8 permutation_inclusion: for right, char in enumerate(text):
pattern='ab'; text='eidbaooo'; m=2; need={'a':1, 'b':1}; window={}; right=0; char='e'

L9 permutation_inclusion: window[char] = window.get(char, 0) + 1
pattern='ab'; text='eidbaooo'; m=2; need={'a':1, 'b':1}; window={'e':1}; right=0; char='e'

L8 permutation_inclusion: for right, char in enumerate(text):
pattern='ab'; text='eidbaooo'; m=2; need={'a':1, 'b':1}; window={'e':1}; right=1; char='i'

L9 permutation_inclusion: window[char] = window.get(char, 0) + 1
pattern='ab'; text='eidbaooo'; m=2; need={'a':1, 'b':1}; window={'e':1, 'i':1}; right=1; char='i'

L8 permutation_inclusion: for right, char in enumerate(text):
pattern='ab'; text='eidbaooo'; m=2; need={'a':1, 'b':1}; window={'e':1, 'i':1}; right=2; char='d'

L9 permutation_inclusion: window[char] = window.get(char, 0) + 1
pattern='ab'; text='eidbaooo'; m=2; need={'a':1, 'b':1}; window={'e':1, 'i':1, 'd':1}; right=2; char='d'

... 9 intermediate state changes omitted ...

L9 permutation_inclusion: window[char] = window.get(char, 0) + 1
pattern='ab'; text='eidbaooo'; m=2; need={'a':1, 'b':1}; window={'d':1, 'b':1, 'a':1}; right=4; char='a'; old='i'

L11 permutation_inclusion: old = text[right - m]
pattern='ab'; text='eidbaooo'; m=2; need={'a':1, 'b':1}; window={'d':1, 'b':1, 'a':1}; right=4; char='a'; old='d'

L12 permutation_inclusion: window[old] -= 1
pattern='ab'; text='eidbaooo'; m=2; need={'a':1, 'b':1}; window={'d':0, 'b':1, 'a':1}; right=4; char='a'; old='d'

L14 permutation_inclusion: del window[old]
pattern='ab'; text='eidbaooo'; m=2; need={'a':1, 'b':1}; window={'b':1, 'a':1}; right=4; char='a'; old='d'

L4 permutation_inclusion: m = len(pattern)
pattern='aab'; text='abb'; m=3

L7 permutation_inclusion: need, window = Counter(pattern), {}
pattern='aab'; text='abb'; m=3; need={'a':2, 'b':1}; window={}

L8 permutation_inclusion: for right, char in enumerate(text):
pattern='aab'; text='abb'; m=3; need={'a':2, 'b':1}; window={}; right=0; char='a'

L9 permutation_inclusion: window[char] = window.get(char, 0) + 1
pattern='aab'; text='abb'; m=3; need={'a':2, 'b':1}; window={'a':1}; right=0; char='a'

L8 permutation_inclusion: for right, char in enumerate(text):
pattern='aab'; text='abb'; m=3; need={'a':2, 'b':1}; window={'a':1}; right=1; char='b'

L9 permutation_inclusion: window[char] = window.get(char, 0) + 1
pattern='aab'; text='abb'; m=3; need={'a':2, 'b':1}; window={'a':1, 'b':1}; right=1; char='b'

L8 permutation_inclusion: for right, char in enumerate(text):
pattern='aab'; text='abb'; m=3; need={'a':2, 'b':1}; window={'a':1, 'b':1}; right=2; char='b'

L9 permutation_inclusion: window[char] = window.get(char, 0) + 1
pattern='aab'; text='abb'; m=3; need={'a':2, 'b':1}; window={'a':1, 'b':2}; right=2; char='b'

Why the solution is correct

The fixed-size update enumerates all possible answer intervals. Equal positive frequency maps are equivalent to equal character multiplicities, so a hit is a permutation and every permutation produces a hit.

Time and space

O(n*u) worst-case time for map comparisons, where u is the number of distinct keys compared (at most O(m)); O(m) space. A fixed-size alphabet makes u constant.

Common mistakes

Claiming unconditional O(n) while comparing arbitrary-size dictionaries hides repeated work. Forgetting multiplicities accepts incorrect windows.

Reasoning card

Transfer exercise

Maintain the number of character-frequency mismatches so each window can be checked in expected O(1) time.