Permutation in String - Solution & Explanation
Problem Statement
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 <= 104s1ands2consist of lowercase English letters.
Approach Overview
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.
Approach 1: Sliding Window with Frequency Count
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.
- Initialize two frequency arrays for s1 and the sliding window in s2 of the same size.
- Slide the window across s2, updating its frequency count and comparing it with s1's frequency count at each step.
- If the window's frequency array matches s1's frequency array, return true, else continue sliding the window.
- If no match is found by the end of s2, return false.
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.
Complexity
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.
Approach 2: Character Mapping Using Hash Map
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.
- Construct a hash map for s1 storing the frequency of each character.
- Use a sliding window to traverse s2, updating the map for each window section.
- Compare the map for each window with the map of s1 and determine if a permutation is found.
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.
Code
Python
JavaScript
Complexity
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.
Approach 3: Sliding Window
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.
Complexity Comparison
| 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 | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Permutation in String - Leetcode 567 - Python • NeetCode • 380,277 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Permutation in String easy or hard?
Permutation in String Python/Java solution
How to solve Permutation in String in O(n)?
What is the best approach for Permutation in String?
Is Permutation in String asked at Google/Amazon/Meta?
What data structure is used in Permutation in String?
What is the time complexity of Permutation in String?
Ready to solve this problem?
Practice Permutation in String with our built-in code editor and test cases.
Practice on FleetCode