Sliding PrefixSum Frequency
IntuitionHow can i know if all chars of word 2 are present in a substring of word1 in O(1) timeApproachComplexity

Time complexity:
O(n)


Space complexity:
O(n
# Intuition\nHow can i know if all chars of word 2 are present in a substring of word1 in O(1) time\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\nO(n)\n\n- Space complexity:\nO(n)\n\n# Code\n```javascript []\n/**\n * @param {string} word1\n * @param {string} word2\n * @return {number}\n */\nvar validSubstringCount = function (word1, word2) {\n  let freqs = new Map();\n  for (let w of word2) {\n    if (freqs.has(w)) {\n      freqs.set(w, freqs.get(w) + 1);\n    } else {\n      freqs.set(w, 1);\n    }\n  }\n  let strap1 = Array(26)\n    .fill(0)\n    .map(() => Array(word1.length).fill(0));\n  for (let w = 0; w < word1.length; w++) {\n    let curr = word1[w].charCodeAt(0) - 97;\n    strap1[curr][w] = 1;\n  }\n  for (let k = 0; k < 26; k++) {\n    for (let i = 1; i < strap1[k].length; i++) {\n      strap1[k][i] = strap1[k][i - 1] + strap1[k][i];\n    }\n  }\n  let p1 = 0;\n  let p2 = word2.length - 1;\n  let res = 0;\n  while (p2 < word1.length) {\n    let is = true;\n    for (let k of Array.from(freqs.keys())) {\n      let targetCharCode = k.charCodeAt(0) - 97;\n      let neededNum = freqs.get(k);\n      if (\n        strap1[targetCharCode][p2] - (strap1[targetCharCode][p1 - 1] || 0) >=\n        neededNum\n      ) {\n        continue;\n      } else {\n        is = false;\n        break;\n      }\n    }\n    if (is) {\n      res += word1.length - p2;\n      p1++;\n      continue;\n    }\n    p2++;\n  }\n  return res;\n};\n```
['JavaScript']