Using sliding window | TC:O(n)| JAVA && Python
Intuition\nUsing the sliding window to count all the substring from right index to end.\n\n# Approach\nUsing the sliding window to maintain left index and right
# Intuition\nUsing the sliding window to count all the substring from right index to end.\n\n# Approach\nUsing the sliding window to maintain left index and right index, if in the window of word1 contains all the letter in word2, all the substring from current window expand to the end of the word1 is valid, so we add len(word1) - rightIndex\n\n# Complexity\n- Time complexity:\nO(len(word1))\n\n- Space complexity:\nO(1)\n\n# Code\n```java []\nclass Solution {\n    public long validSubstringCount(String word1, String word2) {\n        if (word1.length() < word2.length()) {\n            return 0;\n        }\n        int[] cnts = new int[26];\n        for (char c : word2.toCharArray()) {\n            cnts[c -\'a\']--;\n        }\n        for (int i = 0; i < word2.length(); i++) {\n            cnts[word1.charAt(i) - \'a\']++;\n        }\n        int right = word2.length() - 1, left = 0;\n        long res = 0;\n        while (right < word1.length()) {\n            if (isValid(cnts)) {\n                res += (word1.length() - right);\n                cnts[word1.charAt(left) - \'a\']--;\n                left++;\n            } else {\n                right++;\n                if (right < word1.length()) {\n                    cnts[word1.charAt(right) - \'a\']++;\n                }\n            }\n        }\n        return res;\n    }\n\n    private boolean isValid(int[] cnts) {\n        for (int cnt : cnts) {\n            if (cnt < 0) {\n                return false;\n            }\n        }\n        return true;\n    }\n}\n```\n\n```python []\nclass Solution:\n    def validSubstringCount(self, word1: str, word2: str) -> int:\n        if len(word1) < len(word2):\n            return 0\n\n        # Initialize the frequency counts for each letter\n        cnts = [0] * 26\n        \n        # Decrease counts for each character in word2\n        for c in word2:\n            cnts[ord(c) - ord(\'a\')] -= 1\n\n        # Increase counts for the first window of word1\n        for i in range(len(word2)):\n            cnts[ord(word1[i]) - ord(\'a\')] += 1\n\n        right = len(word2) - 1\n        left = 0\n        res = 0\n\n        # Sliding window approach\n        while right < len(word1):\n            if self.isValid(cnts):\n                # If valid, count all substrings from this right index to the end\n                res += (len(word1) - right)\n                cnts[ord(word1[left]) - ord(\'a\')] -= 1\n                left += 1\n            else:\n                right += 1\n                if right < len(word1):\n                    cnts[ord(word1[right]) - ord(\'a\')] += 1\n        \n        return res\n\n    def isValid(self, cnts: list) -> bool:\n        # Check if all values in cnts are non-negative\n        for cnt in cnts:\n            if cnt < 0:\n                return False\n        return True\n```
['Sliding Window', 'Python', 'Java', 'Python3']