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.The key idea in Permutation in String is to determine whether any permutation of one string appears as a contiguous substring in another string. Instead of generating all permutations (which is expensive), we can use a sliding window combined with frequency counting.
First, build a frequency map (or fixed-size array for lowercase letters) for the characters in s1. Then maintain a sliding window of the same length in s2. As the window moves forward using the two pointers technique, update the character counts for the current window.
If at any point the window's character frequency matches the frequency of s1, it means a permutation of s1 exists in s2. This approach avoids recomputation by updating counts incrementally as characters enter and leave the window.
The sliding window ensures that each character is processed only once, leading to an efficient solution with linear time complexity.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sliding Window with Frequency Count | O(n) | O(1) |
CrioDo
Use these hints if you're stuck. Try solving on your own first.
Obviously, brute force will result in TLE. Think of something else.
How will you check whether one string is a permutation of another string?
One way is to sort the string and then compare. But, Is there a better way?
If one string is a permutation of another string then they must have one common metric. What is that?
Both strings must have same character frequencies, if one is permutation of another. Which data structure should be used to store frequencies?
What about hash table? An array of size 26?
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.
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.
1#include <stdbool.h>
2#include <string.h>
3
4bool checkInclusion(char * s1, char * s2) {
5 int len1
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.
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.
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.
1from collections import defaultdict
2
3
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of this problem are frequently asked in technical interviews at FAANG and other top tech companies. It tests understanding of sliding window patterns, hash tables, and efficient string processing.
Sliding window helps efficiently examine all substrings of a fixed length without recomputing character counts from scratch. It updates the counts incrementally as characters enter and leave the window, improving performance.
A frequency array or hash table is commonly used to store character counts. For lowercase English letters, a fixed array of size 26 is usually preferred because it offers constant space and faster access.
The optimal approach uses a sliding window combined with a frequency counter for characters. By maintaining a window of the same length as the first string and updating counts as the window moves, we can efficiently detect if a permutation exists.
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.