🔥BEATS 💯 % 🎯 |✨SUPER EASY BEGINNERS 👏
\n\n---\n\n# Intuition\nTo solve the problem of counting valid substrings of word1 that contain all characters of word2, we can leverage the sliding window tech
![image.png](https://assets.leetcode.com/users/images/7066ee63-1df5-4598-b455-3fab91a541c0_1726985704.1693814.png)\n\n---\n\n# Intuition\nTo solve the problem of counting valid substrings of `word1` that contain all characters of `word2`, we can leverage the sliding window technique. The idea is to maintain a window that counts characters from `word1` and check if it matches the character frequency in `word2`. If a valid window is found, we can count how many valid substrings can be formed from that window.\n\n# Approach\n1. **Frequency Counting**: Create frequency arrays for characters in `word2` and a sliding window in `word1`.\n2. **Sliding Window**: Use two pointers (left and right) to expand and contract the window in `word1`.\n   - Expand the right pointer to include characters in the window.\n   - Check if the current window satisfies the character frequency condition.\n   - If valid, count all possible substrings ending at the right pointer and start shrinking the window from the left to see if it still remains valid.\n3. **Count Valid Substrings**: For each valid position of the right pointer, all characters from the left pointer to the end of `word1` form valid substrings.\n\n# Complexity\n- **Time complexity**:  \n  The overall time complexity is **O(n + m)**, where \\(n\\) is the length of `word1` and \\(m\\) is the length of `word2`. We iterate through `word1` once and update frequencies in constant time.\n  \n- **Space complexity**:  \n  The space complexity is **O(1)**, as we use fixed-size arrays for character frequency (26 for lowercase letters).\n\n---\n\n# Code Implementations\n\n\n```dart []\nclass Solution {\n  // Function to calculate the count of valid substrings\n  int validSubstringCount(String word1, String word2) {\n    // Frequency array for characters in word2\n    List<int> targetFreq = List.filled(26, 0);\n    for (var ch in word2.runes) {\n      targetFreq[ch - \'a\'.runes.first]++;\n    }\n\n    // Frequency array for the sliding window in word1\n    List<int> windowFreq = List.filled(26, 0);\n    int result = 0;\n    int left = 0, matchCount = 0;\n\n    // Iterate through word1 using a sliding window\n    for (int right = 0; right < word1.length; right++) {\n      int charIndex = word1.codeUnitAt(right) - \'a\'.codeUnitAt(0);\n      windowFreq[charIndex]++;\n\n      // If the current character\'s frequency matches that in word2\n      if (windowFreq[charIndex] == targetFreq[charIndex]) {\n        matchCount++;\n      }\n\n      // Shrink window when all required characters are satisfied\n      while (matchCount == targetFreq.where((count) => count > 0).length) {\n        result += word1.length - right;\n\n        int leftCharIndex = word1.codeUnitAt(left) - \'a\'.codeUnitAt(0);\n        if (windowFreq[leftCharIndex] == targetFreq[leftCharIndex]) {\n          matchCount--;\n        }\n        windowFreq[leftCharIndex]--;\n        left++;\n      }\n    }\n\n    return result;\n  }\n}\n```\n\n\n```java []\nclass Solution {\n    public int validSubstringCount(String word1, String word2) {\n        int[] targetFreq = new int[26];\n        for (char ch : word2.toCharArray()) {\n            targetFreq[ch - \'a\']++;\n        }\n\n        int[] windowFreq = new int[26];\n        int result = 0;\n        int left = 0, matchCount = 0;\n\n        for (int right = 0; right < word1.length(); right++) {\n            int charIndex = word1.charAt(right) - \'a\';\n            windowFreq[charIndex]++;\n\n            if (windowFreq[charIndex] == targetFreq[charIndex]) {\n                matchCount++;\n            }\n\n            while (matchCount == getNonZeroCount(targetFreq)) {\n                result += word1.length() - right;\n\n                int leftCharIndex = word1.charAt(left) - \'a\';\n                if (windowFreq[leftCharIndex] == targetFreq[leftCharIndex]) {\n                    matchCount--;\n                }\n                windowFreq[leftCharIndex]--;\n                left++;\n            }\n        }\n        return result;\n    }\n\n    private int getNonZeroCount(int[] freq) {\n        int count = 0;\n        for (int f : freq) {\n            if (f > 0) count++;\n        }\n        return count;\n    }\n}\n```\n\n\n```javascript []\nfunction validSubstringCount(word1, word2) {\n    const targetFreq = Array(26).fill(0);\n    for (let ch of word2) {\n        targetFreq[ch.charCodeAt(0) - \'a\'.charCodeAt(0)]++;\n    }\n\n    const windowFreq = Array(26).fill(0);\n    let result = 0;\n    let left = 0;\n    let matchCount = 0;\n\n    for (let right = 0; right < word1.length; right++) {\n        const charIndex = word1.charCodeAt(right) - \'a\'.charCodeAt(0);\n        windowFreq[charIndex]++;\n\n        if (windowFreq[charIndex] === targetFreq[charIndex]) {\n            matchCount++;\n        }\n\n        while (matchCount === getNonZeroCount(targetFreq)) {\n            result += word1.length - right;\n\n            const leftCharIndex = word1.charCodeAt(left) - \'a\'.charCodeAt(0);\n            if (windowFreq[leftCharIndex] === targetFreq[leftCharIndex]) {\n                matchCount--;\n            }\n            windowFreq[leftCharIndex]--;\n            left++;\n        }\n    }\n    return result;\n}\n\nfunction getNonZeroCount(freq) {\n    return freq.filter(f => f > 0).length;\n}\n```\n\n\n```python []\nclass Solution:\n    def validSubstringCount(self, word1: str, word2: str) -> int:\n        targetFreq = [0] * 26\n        for ch in word2:\n            targetFreq[ord(ch) - ord(\'a\')] += 1\n\n        windowFreq = [0] * 26\n        result = 0\n        left = 0\n        matchCount = 0\n\n        for right in range(len(word1)):\n            charIndex = ord(word1[right]) - ord(\'a\')\n            windowFreq[charIndex] += 1\n\n            if windowFreq[charIndex] == targetFreq[charIndex]:\n                matchCount += 1\n\n            while matchCount == sum(1 for count in targetFreq if count > 0):\n                result += len(word1) - right\n\n                leftCharIndex = ord(word1[left]) - ord(\'a\')\n                if windowFreq[leftCharIndex] == targetFreq[leftCharIndex]:\n                    matchCount -= 1\n                windowFreq[leftCharIndex] -= 1\n                left += 1\n\n        return result\n```\n\n\n```cpp []\n#include <vector>\n#include <string>\n\nclass Solution {\npublic:\n    int validSubstringCount(std::string word1, std::string word2) {\n        std::vector<int> targetFreq(26, 0);\n        for (char ch : word2) {\n            targetFreq[ch - \'a\']++;\n        }\n\n        std::vector<int> windowFreq(26, 0);\n        int result = 0;\n        int left = 0, matchCount = 0;\n\n        for (int right = 0; right < word1.length(); right++) {\n            int charIndex = word1[right] - \'a\';\n            windowFreq[charIndex]++;\n\n            if (windowFreq[charIndex] == targetFreq[charIndex]) {\n                matchCount++;\n            }\n\n            while (matchCount == getNonZeroCount(targetFreq)) {\n                result += word1.length() - right;\n\n                int leftCharIndex = word1[left] - \'a\';\n                if (windowFreq[leftCharIndex] == targetFreq[leftCharIndex]) {\n                    matchCount--;\n                }\n                windowFreq[leftCharIndex]--;\n                left++;\n            }\n        }\n        return result;\n    }\n\nprivate:\n    int getNonZeroCount(const std::vector<int>& freq) {\n        int count = 0;\n        for (int f : freq) {\n            if (f > 0) count++;\n        }\n        return count;\n    }\n};\n```\n\n\n```go []\npackage main\n\nfunc validSubstringCount(word1 string, word2 string) int {\n    targetFreq := make([]int, 26)\n    for _, ch := range word2 {\n        targetFreq[ch-\'a\']++\n    }\n\n    windowFreq := make([]int, 26)\n    result := 0\n    left, matchCount := 0, 0\n\n    for right := 0; right < len(word1); right++ {\n        charIndex := word1[right] - \'a\'\n        windowFreq[charIndex]++\n\n        if windowFreq[charIndex] == targetFreq[charIndex] {\n            matchCount++\n        }\n\n        for matchCount == getNonZeroCount(targetFreq) {\n            result += len(word1) - right\n\n            leftCharIndex := word1[left] - \'a\'\n            if windowFreq[leftCharIndex] == targetFreq[leftCharIndex] {\n                matchCount--\n            }\n            windowFreq[leftCharIndex]--\n            left++\n        }\n    }\n    return result\n}\n\nfunc getNonZeroCount\n\n(freq []int) int {\n    count := 0\n    for _, f := range freq {\n        if f > 0 {\n            count++\n        }\n    }\n    return count\n}\n```\n\n\n```typescript []\nfunction validSubstringCount(word1: string, word2: string): number {\n    const targetFreq = Array(26).fill(0);\n    for (let ch of word2) {\n        targetFreq[ch.charCodeAt(0) - \'a\'.charCodeAt(0)]++;\n    }\n\n    const windowFreq = Array(26).fill(0);\n    let result = 0;\n    let left = 0;\n    let matchCount = 0;\n\n    for (let right = 0; right < word1.length; right++) {\n        const charIndex = word1.charCodeAt(right) - \'a\'.charCodeAt(0);\n        windowFreq[charIndex]++;\n\n        if (windowFreq[charIndex] === targetFreq[charIndex]) {\n            matchCount++;\n        }\n\n        while (matchCount === getNonZeroCount(targetFreq)) {\n            result += word1.length - right;\n\n            const leftCharIndex = word1.charCodeAt(left) - \'a\'.charCodeAt(0);\n            if (windowFreq[leftCharIndex] === targetFreq[leftCharIndex]) {\n                matchCount--;\n            }\n            windowFreq[leftCharIndex]--;\n            left++;\n        }\n    }\n    return result;\n}\n\nfunction getNonZeroCount(freq: number[]): number {\n    return freq.filter(f => f > 0).length;\n}\n```\n\n---\n\n![image.png](https://assets.leetcode.com/users/images/d81a7cee-fa73-41a2-82dc-65bf475d960c_1722267693.3902693.png) {:style=\'width:250px\'}
['C++', 'Java', 'Go', 'TypeScript', 'Python3', 'JavaScript', 'Dart']