Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.
In other words, return true if one of s1's permutations is the substring of s2.
Example 1:
Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").
Example 2:
Input: s1 = "ab", s2 = "eidboaoo" Output: false
Constraints:
1 <= s1.length, s2.length <= 104s1 and s2 consist of lowercase English letters.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.
The main idea is to use a sliding window technique to compare the character frequency of a substring of s2 with the character frequency of s1. If they match, it means s2 contains a permutation of s1.
This solution uses two arrays of size 26 to keep track of the frequency of each letter in s1 and the current window of s2. We first populate the arrays with the frequency of characters in s1 and the initial window of s2. Then, we slide the window over s2 one character at a time, updating the frequency array for the window and checking if it matches the frequency array of s1. If they match, a permutation exists in s2.
Time Complexity: O(n), where n is the length of s2, as each character in s2 is processed once.
Space Complexity: O(1), as the frequency arrays have a fixed size of 26.
Leverage a hash map (or dictionary) to record the character count of s1 and use it to compare with segments of s2. This approach focuses on incremental updates to the map as the window slides over s2.
This Python solution optimizes character comparison by leveraging a hash map to keep track of character frequency changes as the sliding window moves. Instead of full map comparison for each slide, it increments and decrements values while checking conditions, which reduces the overhead of comparing full data structures.
Python
JavaScript
Time Complexity: O(n), where n is the length of s2.
Space Complexity: O(1), since the hash map's size is bounded by the character set size of 26.
We use an array cnt to record the characters and their counts that need to be matched, and a variable need to record the number of different characters that still need to be matched. Initially, cnt contains the character counts from the string s1, and need is the number of different characters in s1.
Then we traverse the string s2. For each character, we decrement its corresponding value in cnt. If the decremented value equals 0, it means the current character's count in s1 is satisfied, and we decrement need. If the current index i is greater than or equal to the length of s1, we need to increment the corresponding value in cnt for s2[i-s1]. If the incremented value equals 1, it means the current character's count in s1 is no longer satisfied, and we increment need. During the traversal, if the value of need equals 0, it means all character counts are satisfied, and we have found a valid substring, so we return true.
Otherwise, if the traversal ends without finding a valid substring, we return false.
The time complexity is O(m + n), where m and n are the lengths of strings s1 and s2, respectively. The space complexity is O(|\Sigma|), where \Sigma is the character set. In this problem, the character set is lowercase letters, so the space complexity is constant.
| Approach | Complexity |
|---|---|
| Sliding Window with Frequency Count | Time Complexity: O(n), where n is the length of s2, as each character in s2 is processed once. |
| Character Mapping Using Hash Map | Time Complexity: O(n), where n is the length of s2. |
| Sliding Window | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Permutation Generation | O(n * m!) | O(m) | Conceptual baseline for understanding permutations; impractical for real constraints |
| Sliding Window with Frequency Count | O(n) | O(1) | Best general solution when character set is fixed (e.g., lowercase letters) |
| Character Mapping Using Hash Map | O(n) | O(k) | Useful when character set is large or not limited to a small alphabet |
Permutation in String - Leetcode 567 - Python • NeetCode • 358,345 views views
Watch 9 more video solutions →Practice Permutation in String with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor