Permutation in String

1. Handle Edge Case

• If s1 is longer than s2, no permutation of s1 can fit inside s2, so return false immediately.

2. Build Frequency Arrays

• Create two arrays of size 26 (one for each lowercase letter): freq1 for s1 and freq2 for the first window of s2.
• Iterate through the first s1.length characters of both strings and populate the frequency counts.

3. Count Initial Matches

• Compare freq1 and freq2 at each of the 26 positions.
• A matches counter tracks how many character slots have equal frequency between the two arrays.
• If matches === 26, all frequencies are equal, meaning the current window is a permutation of s1.

4. Slide the Window Across s2

• For each new position i from s1.length to s2.length - 1:
• Add the new character entering the window on the right. Increment its count in freq2. Update matches — if the count now equals freq1, increment matches; if it just exceeded freq1, decrement matches.
• Remove the character leaving the window on the left. Decrement its count in freq2. Update matches using the same logic.

5. Check After Each Slide

• Before sliding, check if matches === 26. If so, a permutation was found — return true.
• After the loop ends, perform one final check on matches === 26 for the last window position.

6. Return the Result

• If no window matched during the entire traversal, return false.

Key Insight

Instead of comparing two full frequency arrays (O(26)) at every step, we maintain a running matches count that updates in O(1) as each character enters and leaves the window. This keeps the overall complexity at O(n) where n is the length of s2.