Sliding Window and Left and Right Pointer O(n)
Intuition\n\nwriting this explaination for myself\n\nSliding Window and Two Pointer Solution \nCases to cover while solving these kinds of problems \n\nCase 1 :
# Intuition\n\nwriting this explaination for myself\n\nSliding Window and Two Pointer Solution \nCases to cover while solving these kinds of problems \n\nCase 1 : Every substring is a valid one \n`w1 = abcabcabc` and `w1 = abc`\nThen following are the substrings which are valid \n`abcabcabc` = 9 - 3 + 1 = 7 \n`bcabcabc` = 8 - 3 + 1 = 6 \n`cabcabc` = 7 - 3 + 1 = 5\n`abcabc` = 6 - 3 + 1 = 3 \n`bcabc` = 5 - 3 + 1 = 3  \n`cabc` = 4 - 3 + 1 = 2 \n`abc` = 3 - 3 + 1 = 2 \nTotal Substrings = 28 \n\nCase 2 : \n`w1 = abcefabcefgh` and `w2 = abc`\n\nI\'m not solving for the whole string, just mentioning the calculations for corner cases (second while loop in code coveres this). \nThis is the reason we need to keep adding `res += n - j ` while the condition `i < n and is_valid(cnt,prefix_cnts)` is valid. \n\n`efabcefgh` = 9 - 3 + 1 = 7\n`fabcefgh` = 9 - 3 + 1 = 7\n\n\n\n# Complexity\n- Time complexity: $$O(26n)$$ ~ $$O(n)$$\n- Space complexity: $$O(26)$$\n\n# Code\n```python3 []\nclass Solution:\n    def validSubstringCount(self, w1: str, w2: str) -> int:\n        w1,w2 = list(w1),list(w2)\n        n = len(w1)\n        prefix_cnts = Counter(w2)\n        cnt = Counter()\n\n        i = j = res = 0 \n        def is_valid(cnt,pcnt):\n            for w in string.ascii_lowercase:\n                if cnt[w] < pcnt[w]:\n                    return False \n            return True \n        \n        while j < n:\n            cnt[w1[j]] += 1 \n            if is_valid(cnt,prefix_cnts):\n                ok = True \n                while i < n and ok:\n                    res += n - j \n                    curr = w1[i]\n                    cnt[curr] -= 1 \n                    ok = cnt[curr] >= prefix_cnts[curr]\n                    i += 1 \n            j += 1 \n        return res  \n        \n```
['Python3']