simple two pointer approach in O(n) time and O(26) space
Intuition\n Describe your first thoughts on how to solve this problem. \n- The primary task is to count how many substrings in word1 contain all characters of w
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- The primary task is to count how many substrings in word1 contain all characters of word2\n- We use two arrays (represented as mpp), where:\n   - mpp[x][0] keeps track of the frequency of each character in the current sliding window of word1.\n   - mpp[x][1] holds the required frequency of characters based on word2.\n- The sliding window is dynamically adjusted\n    - It expands when the window is too small to contain all characters from word2.\n    - It contracts when all characters are present, counting valid substrings as it does so.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. **Setup the frequency table for word2:**\n    - For each character in word2, increment its frequency count in the mpp array at mpp[character][1].\n    - This helps us keep track of how many occurrences of each character we need in the sliding window from word1.\n1. **Sliding Window:**\n    - Initialize two pointers: l (left) and r (right) to represent the bounds of the sliding window.\n    - Traverse through word1 using the r pointer. For each character at position r, check if it is part of word2:\n        - If the character count in the sliding window (tracked by mpp[x][0]) is less than the count in word2, increment the size (indicating that more of the necessary characters have been found).\n        - If all characters from word2 are found (size == m), begin contracting the window from the left (l) and count all valid substrings.\n1. **Count Valid Substrings:**\n    For each valid window (where the window contains all characters of word2), the count of valid substrings starting at the current l and ending at any position after r is (n - r + 1) (because all substrings starting at l and ending from r to the end of the string are valid).\n1. **Final Cleanup:**\n    After processing the string with the r pointer, handle any remaining valid substrings by continuing to contract the window with the l pointer until it no longer contains all characters of word2.\n\n\n# Complexity\n- Time complexity:O(n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(26)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java []\nimport java.util.*;\n\nclass Solution {\n    public long validSubstringCount(String word1, String word2) {\n        long res = 0;\n        int[][] mpp = new int[26][2]; // To store frequencies of both words\n        int l = 0, r = 0;\n        int n = word1.length();\n        int m = word2.length();\n        int size = 0;\n        \n        // Count frequency of characters in word2\n        for (char ch : word2.toCharArray()) {\n            mpp[ch - \'a\'][1]++;\n        }\n        \n        while (r < n) {\n            // Slide the window while it contains all characters of word2\n            while (size == m && l <= r) {\n                res += (n - r + 1);\n                mpp[word1.charAt(l) - \'a\'][0]--;\n                if (mpp[word1.charAt(l) - \'a\'][1] > 0 && mpp[word1.charAt(l) - \'a\'][0] < mpp[word1.charAt(l) - \'a\'][1]) {\n                    size--;\n                }\n                l++;\n            }\n            // Expand the window\n            if (mpp[word1.charAt(r) - \'a\'][1] > 0 && mpp[word1.charAt(r) - \'a\'][0] < mpp[word1.charAt(r) - \'a\'][1]) {\n                size++;\n            }\n            mpp[word1.charAt(r) - \'a\'][0]++;\n            r++;\n        }\n        \n        // Handle remaining valid substrings\n        while (size == m && l <= r) {\n            res += (n - r + 1);\n            mpp[word1.charAt(l) - \'a\'][0]--;\n            if (mpp[word1.charAt(l) - \'a\'][1] > 0 && mpp[word1.charAt(l) - \'a\'][0] < mpp[word1.charAt(l) - \'a\'][1]) {\n                size--;\n            }\n            l++;\n        }\n        \n        return res;\n    }\n}\n\n```\n```python []\nclass Solution:\n    def validSubstringCount(self, word1: str, word2: str) -> int:\n        res = 0\n        mpp = [[0, 0] for _ in range(26)]  # To store frequencies of both words\n        l, r = 0, 0\n        n = len(word1)\n        m = len(word2)\n        size = 0\n        \n        # Count frequency of characters in word2\n        for ch in word2:\n            mpp[ord(ch) - ord(\'a\')][1] += 1\n        \n        while r < n:\n            # Slide the window while it contains all characters of word2\n            while size == m and l <= r:\n                res += (n - r + 1)\n                mpp[ord(word1[l]) - ord(\'a\')][0] -= 1\n                if mpp[ord(word1[l]) - ord(\'a\')][1] > 0 and mpp[ord(word1[l]) - ord(\'a\')][0] < mpp[ord(word1[l]) - ord(\'a\')][1]:\n                    size -= 1\n                l += 1\n            \n            # Expand the window\n            if mpp[ord(word1[r]) - ord(\'a\')][1] > 0 and mpp[ord(word1[r]) - ord(\'a\')][0] < mpp[ord(word1[r]) - ord(\'a\')][1]:\n                size += 1\n            mpp[ord(word1[r]) - ord(\'a\')][0] += 1\n            r += 1\n        \n        # Handle remaining valid substrings\n        while size == m and l <= r:\n            res += (n - r + 1)\n            mpp[ord(word1[l]) - ord(\'a\')][0] -= 1\n            if mpp[ord(word1[l]) - ord(\'a\')][1] > 0 and mpp[ord(word1[l]) - ord(\'a\')][0] < mpp[ord(word1[l]) - ord(\'a\')][1]:\n                size -= 1\n            l += 1\n        \n        return res\n\n```\n```cpp []\nclass Solution {\npublic:\n    long long validSubstringCount(string word1, string word2) {\n        // this problem can be solved using then concept of sliding window and two pointers\n        long long res=0;\n        vector<pair<int,int>>mpp(26,{0,0});\n        int l,r;\n        l=0;\n        r=0;\n        int n=word1.size();\n        int m=word2.size();\n        int size=0;\n        for(auto ch:word2){\n            mpp[ch-\'a\'].second++;\n        }\n        while(r<n){\n            while(size==m&&l<=r){\n                res+=(n-r+1);\n                mpp[word1[l]-\'a\'].first--;\n                if(mpp[word1[l]-\'a\'].second>0&&mpp[word1[l]-\'a\'].first<mpp[word1[l]-\'a\'].second){\n                    size--;\n                }\n                l+=1;\n            }\n            if(mpp[word1[r]-\'a\'].second>0&&mpp[word1[r]-\'a\'].first<mpp[word1[r]-\'a\'].second){\n                size+=1;\n            }\n            mpp[word1[r]-\'a\'].first++;\n            r+=1;\n        }\n        while(size==m&&l<=r){\n                res+=(n-r+1);\n                mpp[word1[l]-\'a\'].first--;\n                if(mpp[word1[l]-\'a\'].second>0&&mpp[word1[l]-\'a\'].first<mpp[word1[l]-\'a\'].second){\n                    size--;\n                }\n                l+=1;\n        }\n        return res;\n    }\n};\n```\n![ljyaCIu_RMGymk1NhSvUeA.jpg](https://assets.leetcode.com/users/images/3d7dccb1-3f44-47bc-a747-0d57ac617f4d_1726982690.6512058.jpeg)\n
['C++', 'Java', 'Python3']