[Python3] O(nlogn) Prefix count and binary search
Code\npython3 []\nclass Solution:\n    def validSubstringCount(self, word1: str, word2: str) -> int:\n        if len(word1) < len(word2): return 0\n        pref
# Code\n```python3 []\nclass Solution:\n    def validSubstringCount(self, word1: str, word2: str) -> int:\n        if len(word1) < len(word2): return 0\n        prefix, cnt = [[0] * (len(word1) + 1) for _ in range(26)], dict()\n        for i, w in enumerate(word1):\n            for c in range(26): prefix[c][i + 1] = prefix[c][i]\n            prefix[ord(w) - ord(\'a\')][i + 1] += 1\n        for w in word2: cnt[ord(w) - ord(\'a\')] = cnt.get(ord(w) - ord(\'a\'), 0) + 1\n        ans = 0\n        for i in range(len(word1) - len(word2) + 1):\n            ans += len(word1) + 1 - max(bisect_left(prefix[c], prefix[c][i] + cnt[c]) for c in cnt.keys())\n        return ans\n```
['Binary Search', 'Prefix Sum', 'Python3']