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.

Example 1:

Input: s1 = "pq", s2 = "xonrqpkkk"
Output: True
Explanation: "rq" at index 3 is a permutation of s1.

Example 2:

Input: s1 = "pq", s2 = "mpoqrs"
Output: False

Example 3:

Input: s1 = "qpr", s2 = "rqpx"
Output: True
Explanation: "rqp" is a permutation of "qpr".

Constraints:

• 1 <= s1.length, s2.length <= 10^4
• s1 and s2 consist of lowercase English letters.

Solution Breakdown

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="pq", s2="xonrqpkkk": windows "xo", "on", "nr", then "rq" whose counts {r:1, q: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.