Permutation in String

Problem

Given strings s1 and s2, return whether s2 contains a permutation of s1 as a contiguous substring — i.e., some window of s2 that's an anagram of s1.

Examples

Constraints

1 ≤ |s1| ≤ |s2| ≤ 10⁴ · lowercase English letters.

Attempt it first

Two ideas collide here: fixed-size windows (the target length is len(s1) — fixed and known up front) and anagram fingerprints (Hash Tables' Group verb: two strings are anagrams iff their frequency counts match). Combine them: slide a window of size len(s1) across s2, and ask at each position whether the window's fingerprint matches s1's.