567.js

/** ------------------------------------------------------------------------------
 * 
 * 567. Permutation in String
 * Topics: Two Pointers, Hash Table
 * https://leetcode.com/problems/permutation-in-string/description/?envType=daily-question&envId=2024-10-05
 * 
 ------------------------------------------------------------------------------ */
/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
// var checkInclusion = function (s1, s2) {
//   const map = new Map()

//   for (let i = 0; i < s1.length; i++) {
//     map.set(s1[i], map.get(s1[i]) + 1 || 1)
//   }

//   for (let start = 0, end = s1.length - 1; end < s2.length; start++, end++) {
//     console.log("map.has(s2[start])", map.has(s2[start]))
//     console.log("map.has(s2[end])", map.has(s2[end]))

//     console.log(!map.has(s2[start]) || !map.has(s2[end]))

//     if (!map.has(s2[start]) || !map.has(s2[end])) continue

//     let i = start
//     do {
//       map.set(s2[i], map.get(s2[i]) - 1)
//       i++
//     } while (i <= end && map.get(s2[i]))

//     // Check if all chars were in the window
//     if (i > end) return true

//     // Reset the map if any chars in the window didn't match
//     for (let j = start; j < i; j++) map.set(s2[j], map.get(s2[j]) + 1)
//   }

//   return false
// }

/**
 * use object
 */
var checkInclusion = function (s1, s2) {
  if (s1.length > s2.length) return false

  let neededChar = {}

  for (let i = 0; i < s1.length; i++) {
    neededChar[s1[i]] = (neededChar[s1[i]] || 0) + 1
  }

  console.log(neededChar)

  let left = 0
  let right = 0
  let requiredLength = s1.length

  while (right < s2.length) {
    if (neededChar[s2[right]] > 0) requiredLength--

    neededChar[s2[right]]--
    right++

    if (requiredLength === 0) return true

    if (right - left === s1.length) {
      if (neededChar[s2[left]] >= 0) requiredLength++
      neededChar[s2[left]]++
      left++
    }
  }

  return false
}

console.log(checkInclusion("ab", "eidbaooo"))