How to Solve Permutation in String
Permutation in String Introduction
Permutation in String Introduction
The Permutation in String problem asks us to return true if one of s1's permutations is the substring of s2. This problem can be solved using a combination of a sliding window approach and the usage of frequency maps. The frequency map will store the count of each character in the respective strings.
Permutation in String Problem
Permutation in String Problem
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 Inputs and Outputs
Example 1
Input: s1 = "ab", s2 = "eidbaooo"
Output: True
Example 2
Input: s1 = "ab", s2 = "eidboaoo"
Output: False
Permutation in String Solutions
Permutation in String Solutions
To solve this problem, we can use a sliding window approach. First, we create two frequency maps: one for string s1 and one for the current window in string s2. The frequency map will store the count of each character in the respective strings.
We start by initializing the frequency maps for both strings. Then, we set up a window of length equal to the length of s1 in string s2. We compare the frequency maps of s1 and the window of s2. If they are equal, it means that the window in s2 contains a permutation of s1, and we return true. Next, we move the window by one character to the right in s2 and update the frequency maps accordingly. We remove the character that just went out of the window from the frequency map, and we add the new character that came into the window.
We repeat this process until we have exhausted all possible windows in s2. If we have not found a matching permutation, we return false.
from collections import Counter
def checkInclusion(s1, s2):
len_s1 = len(s1)
len_s2 = len(s2)
if len_s1 > len_s2:
return False
freq_s1 = Counter(s1)
freq_window = Counter(s2[:len_s1])
if freq_s1 == freq_window:
return True
for i in range(len_s1, len_s2):
char_out = s2[i - len_s1]
if freq_window[char_out] == 1:
del freq_window[char_out]
else:
freq_window[char_out] -= 1
char_in = s2[i]
freq_window[char_in] += 1
if freq_s1 == freq_window:
return True
return False
# Test case
s1 = "ab"
s2 = "eidbaooo"
result = checkInclusion(s1, s2)
print(result) # Expected output: True1from collections import Counter
2
3def checkInclusion(s1, s2):
4 len_s1 = len(s1)
5 len_s2 = len(s2)
6
7 if len_s1 > len_s2:
8 return False
9
10 freq_s1 = Counter(s1)
11 freq_window = Counter(s2[:len_s1])
12
13 if freq_s1 == freq_window:
14 return True
15
16 for i in range(len_s1, len_s2):
17 char_out = s2[i - len_s1]
18 if freq_window[char_out] == 1:
19 del freq_window[char_out]
20 else:
21 freq_window[char_out] -= 1
22
23 char_in = s2[i]
24 freq_window[char_in] += 1
25
26 if freq_s1 == freq_window:
27 return True
28
29 return False
30
31# Test case
32s1 = "ab"
33s2 = "eidbaooo"
34result = checkInclusion(s1, s2)
35print(result) # Expected output: TrueTime/Space Complexity Analysis
- Time Complexity: O(N), where N is the length of s2, as we iterate through each character once.
- Space Complexity: O(1), as the frequency maps have a fixed size of 26 lowercase letters.
Watch These Related Mock Interviews
About interviewing.io
interviewing.io is a mock interview practice platform. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.
