SLIDE THAT WINDOW
Approach\n Describe your approach to solving the problem. \nThis problem is a typical sliding window problem. \n\nA few key observations:\n1. The order of the l
# Approach\n<!-- Describe your approach to solving the problem. -->\nThis problem is a typical sliding window problem. \n\nA few key observations:\n1. The order of the letters within the substring of `word1` does not matter, as we can rearrage them freely. Therefore only the frequency of the letters selected matters. Thus we keep a `freq` vector array to keep track of the letters\n2. Given observation 1, we can already construct a solution: We will first make the `freq` array store the difference between current selected letters and the frequencies of letters in `word2`, leading to a monotonous value -- the number of letters off from `word2`. Knowing that we have this value that will monotonously increase/decrease as we expand/shrink the window, we have a sliding window solution.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(N)\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(1)\n# Code\n```cpp []\nclass Solution {\npublic:\n    long long validSubstringCount(string word1, string word2) {\n        long long ans = 0;\n        int l = 0;\n\n        vector<int> freq (26, 0);\n        int cnt = 0;\n        for(auto a : word2){\n            freq[a-\'a\']--;\n            cnt --;\n        }\n\n        for(int r = 0; r < word1.length(); r++){\n            char c = word1[r];\n            if(freq[c-\'a\'] < 0) cnt ++;\n            freq[c - \'a\']++;\n\n            while(cnt >= 0 && l <= r){\n                char cl = word1[l];\n                if(--freq[cl-\'a\'] < 0) cnt --;\n                l++;\n            }\n            // cout << l << " " << cnt << endl;\n            if(cnt == -1){\n                ans += l;\n            }\n            \n        }\n        return ans;\n    }\n};\n```
['C++']