Sliding Window + Frequency Dictionary
Complexity\n- Time complexity: O(2xW1 + W2)\n- W1 = length of word1\n- W2 = length of word2\n Add your time complexity here, e.g. O(n) \n\n- Space complexity: O
# Complexity\n- Time complexity: $$O(2xW1 + W2)$$\n- W1 = length of word1\n- W2 = length of word2\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(1)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```python []\nclass Solution(object):\n    def validSubstringCount(self, word1, word2):\n        """\n        :type word1: str\n        :type word2: str\n        :rtype: int\n        """\n        \n        w2_dict = {}\n\n        for c in word2:\n            if c not in w2_dict:\n                w2_dict[c] = 0\n            w2_dict[c] += 1\n        \n        l = 0\n        res = 0\n        w1_dict = {}\n        matching_a = 0\n        for r in range(len(word1)):\n            c = word1[r]\n\n            if c not in w2_dict:\n                continue\n            \n            if c not in w1_dict:\n                w1_dict[c] = 0\n            w1_dict[c] += 1\n\n            if w1_dict[c] == w2_dict[c]:\n                matching_a += 1\n            \n            while matching_a == len(w2_dict):\n                res += len(word1) - r\n                if word1[l] not in w1_dict:\n                    l += 1\n                else:\n                    cl = word1[l]\n                    w1_dict[cl] -= 1\n                    if w1_dict[cl] < w2_dict[cl]:\n                        matching_a -= 1\n                    if w1_dict[cl] == 0:\n                        del w1_dict[cl]\n                    l += 1\n\n\n\n        while matching_a == len(w2_dict):\n            res += 1\n            if word1[l] not in w1_dict:\n                l += 1\n            else:\n                cl = word1[l]\n                w1_dict[cl] -= 1\n                if w1_dict[cl] < w2_dict[cl]:\n                    matching_a -= 1\n                if w1_dict[cl] == 0:\n                    del w1_dict[cl]\n                    l += 1\n        \n        return res\n\n\n\n```
['Python']