Video Explanation -- Journey from O(N*N*C) --> O(N*C*logN) --> O(N*C) --> O(N)
Explanation\n\nClick here for the video\n\n# Code\ncpp []\nvector<int> req(26);\nvector<int> hav(26);\nint matching_cnt = 0;\n\nclass Solution {\n    \n    void
# Explanation\n\n[Click here for the video](https://youtu.be/VX2ruMTnjFk)\n\n# Code\n```cpp []\nvector<int> req(26);\nvector<int> hav(26);\nint matching_cnt = 0;\n\nclass Solution {\n    \n    void Add (char ch) {\n        int ind = ch - \'a\';\n        hav[ind] ++;\n        \n        if (hav[ind] == req[ind]) matching_cnt ++;\n    }\n    \n    void Remove (char ch) {\n        int ind = ch - \'a\';\n        hav[ind] --;\n        \n        if (hav[ind] == req[ind]-1) matching_cnt --;\n    }\n    \npublic:\n    long long validSubstringCount(string word1, string word2) {\n        for (int i = 0; i < 26; i ++) req[i] = hav[i] = 0;\n        matching_cnt = 0;\n        \n        for (auto c : word2) req[c-\'a\'] ++;\n        for (int i = 0; i < 26; i ++)\n            if (req[i] == 0) matching_cnt ++;\n        \n        int n = word1.length();\n        long long ans = 0;\n        int l = 0, r = -1;\n        \n        while (l < n) {\n            while (r+1 < n && matching_cnt < 26) {\n                r ++;\n                Add (word1[r]);\n            }\n            \n            if (matching_cnt == 26) ans += (n - r);\n            \n            Remove (word1[l]);\n            l ++;\n        }\n        return ans;\n    }\n};\n```
['C++']