Permutation in String

Problem

Given two lowercase strings s1 and s2, determine whether some contiguous substring of s2 is a rearrangement of s1, that is, whether s2 contains a substring with exactly the same letters, with the same multiplicities, as s1.

• Each string has between 1 and 20,000 characters.
• Only lowercase a-z appears in either string.

Examples

• s1 = "gh", s2 = "nlghdd" → True. The substring "gh" appears directly.
• s1 = "world", s2 = "dlrrowoowl" → False. Every five-letter window is missing at least one of the required letters or has a duplicate.
• s1 = "xyz", s2 = "zyx" → True. All of s2 is a rearrangement of s1.

Hints

1. Every candidate substring has the same length as s1. What does that fix about the window?
2. Two strings are rearrangements of each other exactly when their letter counts agree. Can you update a count table as the window slides by one?
3. Fixed-size sliding window over s2 with a 26-entry count array; maintain how many of the 26 letters currently match s1's count, so each step is O(1).