Effortless Sliding Window Trick !!! Striver's Approach 🔥🫣🤯
Approach\nExplanation of Code:\n\n1.Frequency Count: count stores the frequency of each character in word2.\n2.Sliding Window: The prefix array keeps track of t
# Approach\nExplanation of Code:\n\n1.Frequency Count: count stores the frequency of each character in word2.\n2.Sliding Window: The prefix array keeps track of the character frequencies in the current window from j to i.\n3.Validity Check: The function isvalid compares the prefix (window\'s frequency) with count (required frequency for word2). If the window is valid, it counts all substrings starting from j to the end of word1.\n4.Final Answer: For every valid window, we count how many substrings can start from j and include all substrings from i to n-1\n\n# Complexity\n- Time complexity:O(n)\n\n- Space complexity:O(26)+O(26)~constant\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    bool isvalid(vector<int>& prefix, vector<int>& count) {\n    for (int i = 0; i < 26; i++) {\n        if (prefix[i] < count[i]) {\n            return false;\n        }\n    }\n    return true;\n}\n    long long validSubstringCount(string word1, string word2) {\n        vector<int>count(26,0);\n        for(int i=0;i<word2.size();i++){\n            count[word2[i]-\'a\']++;\n        }\n        long long ans=0;\n        int i=0;\n        int j=0;\n        int n=word1.size();\n        int m=word2.size();\n        vector<int>prefix(26,0);\n        while(i<n){\n            prefix[word1[i]-\'a\']++;\n            while(isvalid(prefix,count)&&j<=i){\n                ans+=n-i;\n                prefix[word1[j]-\'a\']--;\n                j++;\n            }\n            i++;\n        }\n        return ans;\n    }\n};\n```
['Hash Table', 'Sliding Window', 'Prefix Sum', 'C++']