Permutation in String

Check whether any substring has the same letter counts as the pattern.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Permutation in String: Slide one width-2 window over "eidbaooo"; add R, remove the outgoing L character, then compare counts.

Input and goalCheck whether any substring has the same letter counts as the pattern.

Count the first width-2 windowpattern = "ab" needs a:1,b:1. text[0..1] = "ei" has e:1,i:1, so the counters differ.

Le0Ri1d2b3a4o5o6o7

range[0..1] = "ei"comparisone:1,i:1 != a:1,b:1

saved stateneeda:1, b:1windowe:1, i:1

Recognize it

Use it when a contiguous match may appear in any order: equal multisets require equal length, so only windows whose width equals the pattern length can qualify.

Keep true

Before each comparison, window contains exactly text[R - pattern_length + 1..R], because the new right character was added and the one character that fell off the left was removed.

Reuse it

When every candidate has a known width, maintain its summary by adding the entering item and removing the outgoing item; compare summaries instead of rebuilding or enumerating arrangements.

Pattern: Fixed-size sliding window.

Simple idea: A matching substring must have the same length as the pattern. Keep letter counts for one window of that size. Add the new right character and remove the old left character.

from collections import Counter

def check_inclusion(pattern: str, text: str) -> bool:
   if len(pattern) > len(text):
      return False

   need = Counter(pattern)
   window = Counter(text[: len(pattern)])
   if window == need:
      return True

   for right in range(len(pattern), len(text)):
      window[text[right]] += 1
      left_char = text[right - len(pattern)]
      window[left_char] -= 1
      if window[left_char] == 0:
         del window[left_char]
      if window == need:
         return True
   return False

Cost: $O(n)$ time for a fixed alphabet and $O(k)$ space.