Sliding Windows Solution
Intuition\n Describe your first thoughts on how to solve this problem. \nSolution from here:https://leetcode.com/problems/count-substrings-that-can-be-rearrange
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nSolution from here:https://leetcode.com/problems/count-substrings-that-can-be-rearranged-to-contain-a-string-i/solutions/5818284/sliding-window-with-example-walkthrough/\nI just want to record what I\'ve learn. \n\n# Complexity\n- Time complexity: O(Len(W1))\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(1)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    long long validSubstringCount(string word1, string word2) {\n\n       /*\n       [0,2],[1,3],[2,4],[3,5]\n       [0,3],[1,4],[2,5]\n       [0,4],[1,5]\n       [0,5]\n       */\n        int word1Freq[26] = {0};\n        int word2Freq[26] = {0};\n       //;memset(word1Freq, 0, sizeof(word1Freq));\n        for(auto&c : word2){\n            word2Freq[c - \'a\']+=1;\n        }\n        int w1Len = word1.size();\n        int w2Len = word2.size();\n        int remainLen = w2Len;\n        int start = 0;\n        long long ans = 0;\n        for(int end = 0; end < w1Len; ++end){\n            if(word1Freq[word1[end] - \'a\'] < word2Freq[word1[end] - \'a\']){\n               remainLen-=1; \n            }\n            word1Freq[word1[end] - \'a\']+=1;\n            while(remainLen == 0){\n                //aabcde, target = \'abc\'\n                //ans+=6-3 = 3 means can add postfix c,cd,cde\n                //start+=1 and remainLen still equal 0 (vaild)\n                //ans+=6-3 same as prev reason\n                ans+=w1Len-end;\n                word1Freq[word1[start] - \'a\']-=1;\n                if(word1Freq[word1[start] - \'a\'] < word2Freq[word1[start] - \'a\']){\n                    remainLen+=1;\n                }\n                start+=1;\n            }\n        }\n\n\n        return ans;\n    }\n};\n```
['Sliding Window', 'C++']