π‘ Problem Introduction
LeetCode 567: Check if string s2 contains any permutation of s1.
- Input:
s1 = "ab",s2 = "eidbaooo" - Output:
true(because "ba" is a permutation ofs1and appears ins2)
π§ Initial Brute Force Approach
First approach was to brute force enumerate all substrings of length s1.length in s2, then compare their frequency maps with s1's frequency map.
function getCharFrequencyMap(s) {
const map = new Map()
for (const ch of s) {
map.set(ch, (map.get(ch) || 0) + 1)
}
return map
}
function isSameFrequencyMap(map1, map2) {
if (map1.size !== map2.size) return false
for (const [key, val] of map1.entries()) {
if (map2.get(key) !== val) return false
}
return true
}
var checkInclusion = function(s1, s2) {
const map = getCharFrequencyMap(s1)
let left = 0, right = s1.length - 1
while (right < s2.length) {
const tmpMap = getCharFrequencyMap(s2.slice(left, right + 1))
if (isSameFrequencyMap(map, tmpMap)) return true
left++
right++
}
return false
}
- β Passes sample cases
- β Rebuilds
Mapfor each substring, performance bottleneck due to repetitive counting
β Optimization: Sliding Window + Map
Using sliding window technique with a Map window to track character frequencies in current window, and maintaining a valid variable to count characters with completely matched frequencies.
var checkInclusion = function(s1, s2) {
const map = getCharFrequencyMap(s1)
const window = new Map()
let left = 0, right = 0, valid = 0
while (right < s2.length) {
const ch = s2[right]
right++
if (map.has(ch)) {
window.set(ch, (window.get(ch) || 0) + 1)
if (window.get(ch) === map.get(ch)) {
valid++
}
}
while (right - left >= s1.length) {
if (valid === map.size) return true
const del = s2[left]
left++
if (map.has(del)) {
if (window.get(del) === map.get(del)) {
valid--
}
window.set(del, window.get(del) - 1)
}
}
}
return false
}
π Optimization Comparison:
| Criteria | Brute Force | Sliding Window |
|---|---|---|
| Substring Frequency Counting | Recount every time | Sliding update, O(1) complexity |
| Overall Time Complexity | O(n Γ m) | O(n) |
| Performance | Works for small samples | Stable and efficient for large samples |
π§ Summary
- For substring matching problems, sliding window + frequency counting + valid counter is a performance game-changer.
- Always cultivate the optimization mindset of "avoiding redundant computations".
- This solution uses
Mapfor frequency counting, which works for all character sets. Can also be optimized to fixed-length array for O(26) space.
If you encounter performance issues while solving problems, take a moment to think about whether you can introduce state caching or sliding window techniques π.