Count permutations of S in B in O(B)

getPurmutations.ts

function getPurmutations(s: string, b: string) {
  if (s.length > b.length) {
    return 0
  }

  const desiredChars = {}
  const possiblePurmutations = {} // contain the starting index for the purmutation, and the remaining characters that need to be found

  let purmutationsCount = 0
  for (const char of s) {
    if (!desiredChars[char]) {
      desiredChars[char] = 1
    } else {
      desiredChars[char]++
    }
  }

  for (let i = 0; i < b.length; ++i) {
    const char = b[i]

    if (desiredChars[char]) {
      // Creates a new possible purmutation starting at current index
      possiblePurmutations[i] = {
        desiredChars: Object.assign({}, desiredChars),
        charsFound: 0
      }

      // Updates any previous purmutations starting at index - s.length
      for (let reverseIndex = 0; reverseIndex < s.length; reverseIndex++) {
        if (!possiblePurmutations[i - reverseIndex]) {
          continue
        }

        const charCountToFulfill = possiblePurmutations[i - reverseIndex].desiredChars[char]

        if (charCountToFulfill > 0) {
          possiblePurmutations[i - reverseIndex].desiredChars[char]--
          possiblePurmutations[i - reverseIndex].charsFound++
        } else {
          delete possiblePurmutations[i - reverseIndex]
        }
      }
    } else {
      // Deletes all pending purmutation calculations if the current character is not from param s
      for (let reverseIndex = 1; reverseIndex < s.length; reverseIndex++) {
        delete possiblePurmutations[i - reverseIndex]
      }
    }
  }

  for (let index = 0; index < b.length; ++index){
    if (possiblePurmutations[index] && possiblePurmutations[index].charsFound === s.length) {
      purmutationsCount++
    }
  }

  return purmutationsCount
}