The goal is to determine if one string contains a permutation of another string. You can solve this problem efficiently using a sliding window approach and hash table. Instead of checking every substring, keep track of character counts within the window and update dynamically as you move through the string.
Problem Statement
Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise. A permutation is any rearrangement of s1's characters.
For example, s1 = 'ab' and s2 = 'eidbaooo'. Since s2 contains a substring 'ba', which is a permutation of s1, the result is true. Otherwise, s2 may not have any valid permutations of s1.
Examples
Example 1
Input: s1 = "ab", s2 = "eidbaooo"
Output: true
s2 contains one permutation of s1 ("ba").
Example 2
Input: s1 = "ab", s2 = "eidboaoo"
Output: false
Example details omitted.
Constraints
- 1 <= s1.length, s2.length <= 104
- s1 and s2 consist of lowercase English letters.
Solution Approach
Sliding Window with Hash Table
Use a sliding window of size equal to s1's length. Maintain a hash table to track the frequency of characters in the window. Move the window across s2, updating the hash table dynamically.
Two-Pointer Technique
By using two pointers to track the window's bounds and moving the window through s2, you can compare the frequency of characters in the current window with those in s1, without recalculating from scratch each time.
Efficient Comparison
Instead of repeatedly comparing full substrings, compare only the frequencies of characters. This reduces the time complexity to O(n), where n is the length of s2, ensuring the algorithm runs efficiently.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | O(l_1 + (l_2 - l_1)) \approx O(l_2) |
| Space | O(1) |
The time complexity is O(l2), where l2 is the length of s2. The space complexity is O(1), as the hash table will store at most 26 characters for lowercase English letters.
What Interviewers Usually Probe
- Can the candidate optimize the brute force approach?
- Does the candidate demonstrate understanding of sliding window and hash table concepts?
- Is the candidate able to explain the time complexity and avoid redundant operations?
Common Pitfalls or Variants
Common pitfalls
- Forgetting to handle character frequencies properly within the window.
- Inefficiently recalculating the hash table for each new substring.
- Failing to recognize the need for dynamic updates of the window.
Follow-up variants
- Different constraints on the sizes of s1 and s2.
- Handling strings with larger character sets (e.g., uppercase letters).
- Modifying the problem to check for permutations in multiple substrings of s2.
How GhostInterview Helps
- GhostInterview's approach will help you master efficient sliding window techniques while understanding invariant tracking through hash tables.
- By focusing on this pattern, GhostInterview ensures you're ready for optimization-focused interviews and avoids common inefficiencies like brute force.
- With step-by-step hints and explanations, GhostInterview provides clarity on key trade-offs, boosting your problem-solving confidence.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the optimal solution to the Permutation in String problem?
The optimal solution uses a sliding window approach combined with a hash table to track character frequencies and compare the window with the target string.
How does the sliding window help in solving this problem?
The sliding window allows you to examine each possible substring in s2 without recalculating character counts from scratch, leading to a more efficient solution.
Can brute force work for the Permutation in String problem?
Brute force may work, but it will lead to time limit exceeded (TLE) errors for large inputs. A sliding window approach is far more efficient.
What are the edge cases for the Permutation in String problem?
Edge cases include very short strings, strings where no permutation exists, or strings with identical characters.
What is the time complexity of the sliding window approach for this problem?
The time complexity is O(n), where n is the length of s2, since we scan through s2 just once while updating the window dynamically.
Need direct help with Permutation in String instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Permutation in String from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Find the longest string in an array that is not a subsequence of any other string, using array scanning and hash checks efficiently.
Open problem page#438 Find All Anagrams in a StringFind all starting indices of p's anagrams in s using sliding window and hash table approach.
Open problem page#424 Longest Repeating Character ReplacementFind the length of the longest substring after at most k replacements using a sliding window and character count tracking.
Open problem page