Permutation in String
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 the permutations of s1 is a substring of s2.
Constraints:
- The input strings only contain lowercase English letters.
- 1 <= s1.length, s2.length <= 10^5
- s1 and s2 consist of only lowercase English letters.
Examples:
Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: One possible permutation of s1 in s2 is "ba".
Solutions
Sliding Window
The solution uses a sliding window approach to check if a permutation of s1 exists in s2. It maintains two frequency arrays, s1Count and s2Count, to keep track of the characters in s1 and the current window of s2. The matches variable keeps track of the number of characters that have the same frequency in both s1 and the current window of s2. The solution iterates over the string s2, expanding the window to the right and updating the frequency arrays and matches variable accordingly. If at any point the number of matches is equal to the length of s1, it means a permutation of s1 has been found in s2, and the solution returns true.
function checkInclusion(s1, s2) {
let s1Len = s1.length;
let s2Len = s2.length;
if (s1Len > s2Len) return false;
let s1Count = {};
let s2Count = {};
for (let i = 0; i < s1Len; i++) {
s1Count[s1[i]] = (s1Count[s1[i]] || 0) + 1;
s2Count[s2[i]] = (s2Count[s2[i]] || 0) + 1;
}
let matches = 0;
for (let char in s1Count) {
if (s1Count[char] === s2Count[char]) matches++;
}
let left = 0;
for (let right = s1Len; right < s2Len; right++) {
if (matches === Object.keys(s1Count).length) return true;
s2Count[s2[left]]--;
if (s2Count[s2[left]] === 0) {
matches--;
} else if (s2Count[s2[left]] === s1Count[s2[left]]) {
matches++;
}
s2Count[s2[right]] = (s2Count[s2[right]] || 0) + 1;
if (s2Count[s2[right]] === s1Count[s2[right]]) {
matches++;
} else if (s2Count[s2[right]] > s1Count[s2[right]]) {
matches--;
}
left++;
}
return matches === Object.keys(s1Count).length;
}
Follow-up:
How would you modify the solution to handle cases where s1 and s2 contain uppercase letters or special characters?
