Permutation in String

Problem

An intrusion-detection system flags suspicious character sequences: a message triggers an alert if any contiguous block of characters is a rearrangement of a known threat signature. Given the threat signature s1 and a message string s2, return true if any permutation of s1 appears as a contiguous substring of s2.

Input: s1 = "ab",  s2 = "eidbaooo"  → True   ("ba" at index 3)
Input: s1 = "ab",  s2 = "eidboaoo"  → False
Input: s1 = "adc", s2 = "dcda"      → True   ("dca" is a permutation of "adc")

Solution

Approach: Fixed-size sliding window with frequency-map comparison.

Every permutation of s1 has exactly the same character multiset as s1, so a permutation of s1 exists in s2 iff some window of s2 of length k = len(s1) has identical character frequencies. Build s1_count = Counter(s1) once, then seed window_count = Counter(s2[:k]) for the first window and compare. To advance, slide the fixed window one position: add the entering character s2[end], decrement the leaving character s2[end - k], and delete its key when its count hits 0 so that Counter equality stays exact (a leftover 0 entry would make == fail). After each slide, window_count == s1_count answers whether that window is a permutation. Deleting zero-count keys is what lets a plain == comparison work - otherwise you would compare {'a': 0, 'b': 1} against {'b': 1} and get False.

Trace s1="ab", s2="eidbaooo": windows "ei", "id", "db", then "ba" whose counts {b:1, a:1} equal s1_count - return True.

Edge cases: If k > len(s2) no window fits, so return False immediately. s1 == s2 checks the single full-length window. A length-1 pattern matches on the seeded window before the loop.

Complexity: O(n) time, O(1) space - the loop runs n times and each Counter comparison is bounded by the 26-letter alphabet; the two counters never exceed alphabet size.