LeetCode 567 Optimization Journey: From Brute Force to Sliding Window

💡 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 of s1 and appears in s2)

🚧 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 Map for 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:

🧠 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 Map for 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 😉.