Sliding window and frequency counting
Intuition\n- slide window [i, j) on word1 and count/compare its char frequency to word2\n- append \'z\'+1 to word1 to avoid edge case\n \n\n# Code\ncpp []\nclas
# Intuition\n- slide window `[i, j)` on `word1` and count/compare its char frequency to `word2`\n- append `\'z\'+1` to `word1` to avoid edge case\n \n\n# Code\n```cpp []\nclass Solution {\npublic:\n    long long validSubstringCount(string word1, string word2) {\n        array<int, 27> freq1 = {}, freq2 = {};\n        for(auto c : word2) freq2[c-\'a\']++;\n\n        auto valid = [&freq1, freq2] () {\n            for(int i = 0; i < 26; ++i)\n                if(freq1[i] < freq2[i])\n                    return false;\n            return true;\n        };\n        long long count = 0;\n        word1.push_back(\'z\'+1);\n        for(int i = 0, j = 0, sz = word1.size(); j < sz;) {\n            if(valid()) {\n                count += sz - j; \n                freq1[word1[i++]-\'a\']--;\n            }\n            else\n                freq1[word1[j++]-\'a\']++;\n        }\n        return count;\n    }\n};\n```
['C++']