567. Permutation in String Medium
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
Approach
Input: Two strings s1 and s2.
Output: Return boolean indicating whether there exists a substring in s2 that is a permutation of s1.
This problem falls under the Fixed-length Sliding Window category.
We can use a sliding window of length equal to s1 exploring across s2, tracking character frequencies within the window in real-time. Use two counters (arrays or hash maps) to record occurance frequencies of each letter in s1 and the current window, respectively. With each window movement, just update the counts for the characters entering and leaving, and then compare if the two tracking states are equivalent. If, at any moment, the character frequency in the window wholly equates with that of s1, it means an effective permutation is localized, returning True. If False is yielded initially, search ends indicating failure.
The trickiest part revolves around recognizing logic employing arrays or hash maps to contrast character occurences in a sliding window.
Implementation
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
len_s1, len_s2 = len(s1), len(s2)
if len_s1 > len_s2:
return False
count1 = [0] * 26 # Stat mapping for each char representation in s1
count2 = [0] * 26 # Character stat distribution inside sliding window on s2
for i in range(len_s1):
count1[ord(s1[i]) - ord('a')] += 1
count2[ord(s2[i]) - ord('a')] += 1
# Start sliding window
for i in range(len_s2 - len_s1):
if count1 == count2:
return True
# Strip leftmost char, embed the new right char
count2[ord(s2[i]) - ord('a')] -= 1
count2[ord(s2[i + len_s1]) - ord('a')] += 1
# Do not forget to correlate the assessment on the absolute final window frame
return count1 == count2// Judge if s2 encapsulates any permutation of s1
var checkInclusion = function(s1, s2) {
const n1 = s1.length; // Length of s1
const n2 = s2.length; // Length of s2
if (n1 > n2) return false; // If s1 tops s2 in length, impossibility assumed - returning false strictly
// Record tally sheet structure for exactly 26 alphabetical entries
const count1 = Array(26).fill(0); // Frequency sheet of s1 characters
const count2 = Array(26).fill(0); // Frequency profile captured dynamically in window
// Booting up calculations: count up preceding character arrays up to limit n1 across s1 and s2 mutually
for (let i in s1) {
count1[s1[i].charCodeAt(0) - 'a'.charCodeAt(0)] += 1;
count2[s2[i].charCodeAt(0) - 'a'.charCodeAt(0)] += 1;
}
// Commencing sliding: keeping window stretch stable exactly measuring n1 progressing left to right
for (let j = 0; j < n2 - n1; j++) {
// Evaluate arrays dynamically against correlation criteria indicating complete hit
if (isEqual(count1, count2)) {
return true;
}
// Shift Right sequence mapping: subtract left tip representation and include right side representation appended
count2[s2[j].charCodeAt(0) - 'a'.charCodeAt(0)] -= 1; // Remove relative left element
count2[s2[j + n1].charCodeAt(0) - 'a'.charCodeAt(0)] += 1; // Inject relative right element
}
// For final loop culmination, perform ultimate review for equality post last shift frame mapped
return isEqual(count1, count2);
};
// Tool matching correlation perfectly connecting identically proportioned array objects
function isEqual(list1, list2) {
for (let i in list1) {
if (list1[i] !== list2[i]) {
return false; // Yield off when any mismatch flagged out
}
}
return true; // Unblemished completion guarantees equivalence
}Complexity Analysis
- Time Complexity: O(n) where n is size of s2
- Space Complexity: O(1) or O(26) strictly bounding character counts mappings