Permutation in String 🧠
LeetCode Link: Permutation in String
Difficulty: Medium
Problem Explanation 📝
Problem: LeetCode 567 - Permutation in String
Description:
Given two strings s1
and s2
, return true
if s2
contains the permutation of s1
.
In other words, one of the first string's permutations is the substring of the second string.
Intuition:
To check if s2
contains a permutation of s1
, we can use a sliding window approach.
- We initialize two frequency maps,
freq1
andfreq2
, to store the frequencies of characters ins1
and the sliding window ofs2
. - If the frequencies in
freq1
andfreq2
are equal, then it meanss2
contains a permutation ofs1
. - By sliding the window through
s2
, we can keep track of the frequencies of characters in the current window and compare them with the frequencies infreq1
.
Approach:
- We start by checking if the length of
s1
is greater thans2
. If it is, then it's not possible fors2
to contain a permutation ofs1
, so we returnfalse
. - We initialize two arrays,
freq1
andfreq2
, to store the frequencies of characters ins1
and the sliding window ofs2
.
- Both arrays should have a size of 26 to represent the lowercase English letters.
- We iterate through the first
s1.size()
characters ofs2
to initialize the frequencies in both arrays. - We initialize two pointers,
L
andR
, representing the left and right ends of the window, respectively. - If the frequencies in
freq1
andfreq2
are equal, we returntrue
becauses2
contains a permutation ofs1
. - We iterate from index
s1.size()
tos2.size()
using the sliding window approach:
- If the frequency of the character at index
L
infreq2
is 1, we remove it fromfreq2
since we will incrementL
later. - Otherwise, we decrement the frequency of the character at index
L
infreq2
since we will incrementL
. - We increment the frequency of the character at index
R
infreq2
since we have added a new character to the window. - We increment
L
to slide the window to the right. - If the frequencies in
freq1
andfreq2
are equal, we returntrue
.
- If no permutation is found after iterating through
s2
, we returnfalse
.
⌛ Time Complexity:
The time complexity is O(n), where n is the length of s2
. We iterate through s2
once using the sliding window approach.
💾 Space Complexity:
The space complexity is O(1) as both freq1
and freq2
have a fixed size of 26, representing lowercase English letters.
Solutions 💡
Cpp 💻
class Solution {
public:
bool checkInclusion(string s1, string s2) {
if (s1.size() > s2.size()) {
return false;
}
vector<int> freq1(26, 0);
vector<int> freq2(26, 0);
for (int i = 0; i < s1.size(); i++) {
freq1[s1[i] - 'a']++;
freq2[s2[i] - 'a']++;
}
int L = 0;
if (freq1 == freq2) {
return true;
}
for (int R = s1.size(); R < s2.size(); R++) {
if (freq2[s2[L] - 'a'] == 1) {
freq2[s2[L] - 'a'] = 0;
} else {
freq2[s2[L] - 'a']--;
}
freq2[s2[R] - 'a']++;
L++;
if (freq1 == freq2) {
return true;
}
}
return false;
}
};
Python 🐍
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
if len(s1) > len(s2):
return False
char_freq_s1 = {}
for char in s1:
char_freq_s1[char] = char_freq_s1.get(char, 0) + 1
left, right = 0, 0
char_freq_temp = {}
while right < len(s2):
char_freq_temp[s2[right]] = char_freq_temp.get(s2[right], 0) + 1
if right - left + 1 == len(s1):
if char_freq_temp == char_freq_s1:
return True
char_freq_temp[s2[left]] -= 1
if char_freq_temp[s2[left]] == 0:
del char_freq_temp[s2[left]]
left += 1
right += 1
return False