💡 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 😉.