Permutation in String - Video Solutions

Problem Overview: Given two strings s1 and s2, determine whether any permutation of s1 appears as a substring inside s2. In practice, you need to detect whether some contiguous window of s2 contains exactly the same character counts as s1.

Approach 1: Brute Force Permutation Check (O(n * m!) time, O(m) space)

The naive solution generates every permutation of s1 and checks whether it exists in s2. For a string of length m, there are m! permutations, and each one requires a substring search in s2. Even with optimizations, this quickly becomes infeasible for typical constraints. This approach is useful only as a conceptual baseline to understand that the problem is essentially about matching character frequencies rather than exact order.

Approach 2: Sliding Window with Frequency Count (O(n) time, O(1) space)

The optimal solution treats the problem as a fixed-size window comparison. First compute a frequency count for characters in s1. Then iterate through s2 using a window of length s1.length(). For each step, update the frequency of the entering character and remove the frequency of the exiting character. If the frequency arrays match, the current window is a permutation of s1. Because the alphabet is limited (typically 26 lowercase letters), comparing counts is constant time. This technique relies on the sliding window pattern and often pairs with two pointers to maintain the window boundaries efficiently.

Approach 3: Character Mapping Using Hash Map (O(n) time, O(k) space)

This variation replaces the fixed-size array with a hash map that tracks how many characters are still required to match s1. As you expand the window across s2, decrement counts for seen characters. When a count reaches zero, that character requirement is satisfied. If the window grows larger than s1, increment the count of the character leaving the window. When all required characters are satisfied simultaneously, a valid permutation exists. This approach works well when the character set is large or unknown and demonstrates the use of a hash table for dynamic frequency tracking.

Recommended for interviews: Interviewers typically expect the sliding window frequency-count solution. It demonstrates recognition of substring pattern matching and efficient window maintenance in O(n) time. Mentioning the brute force permutation idea shows you understand the underlying requirement, but implementing the optimized window approach proves you can apply common string-processing patterns effectively.