Optimized Approach - O(n) Time Complexity with Constant Space
Intuition\nWe need to find all substrings in word1 that contain every character present in word2 with the exact required frequency. Starting from the first inde
# Intuition\nWe need to find all substrings in word1 that contain every character present in word2 with the exact required frequency. Starting from the first index of word1, we\'ll use a sliding window approach to count the characters from word2. \n\nAs soon as our window contains all the necessary characters with their required counts, we\'ll determine how many extra characters exist before the current start index and how many potential characters remain after the current end index. By multiplying these two values, we get the total number of valid substrings that can be formed. We then add this count to our answer. Afterward, we slide the window further to the right and repeat the process until we\'ve checked all possible substrings.\n\n# Approach\nSliding Window approach\n\n# Complexity\n- Time complexity:\nO(n)\n\n- Space complexity:\nO(26)\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    long long validSubstringCount(string word1, string word2) {\n\n        vector<int> v(26,0);\n        vector<int> v1(26,0);\n\n        long long ans =0;\n\n        for(auto it:word2) v[it-\'a\']++;\n\n        int i=0,j=0,ct=0;\n\n        while(j<word1.size()){\n            if(v[word1[j]-\'a\'] && v1[word1[j]-\'a\'] < v[word1[j]-\'a\']){\n                ct++;\n            }\n\n            v1[word1[j]-\'a\']++;\n\n            if(ct==word2.size()){\n                int back = 0;\n\n                while(v1[word1[i]-\'a\']>v[word1[i]-\'a\']){\n                    v1[word1[i]-\'a\']--;\n\n                    back++;\n                    i++;\n                } \n\n                back++;\n\n                int front = word1.size() - j;\n                ans += (front * back);\n\n                v1[word1[i]-\'a\']--;\n                ct--;\n\n                i++;\n            }\n\n            j++;\n        }\n\n        return ans;\n    }\n};\n\n//aabbabcabc\n```
['Sliding Window', 'C++']