The tell: Does a fixed-length anagram of one string appear inside another?
How you get there
1A permutation has a fixed length, so the window size is known and constant.
2Slide it one character at a time, incrementing the entrant and decrementing the leaver.
3Compare counts, which is O(26) per step and therefore constant.
Solution
Python
from collections import Counter
def check_inclusion(s1: str, s2: str) -> bool:
n, m = len(s1), len(s2)
if n > m:
return False
need = Counter(s1)
window = Counter(s2[:n])
if window == need:
return True
for i in range(n, m):
window[s2[i]] += 1
left = s2[i - n]
window[left] -= 1
if window[left] == 0:
del window[left] # keep Counter equality meaningful
if window == need:
return True
return False
Time
O(n)
Space
O(1)
What goes wrong
Leaving zero-count keys in the Counter makes == fail even when the multisets match.