Esay sliding window approach
We need to store the freq of all chars of word2 in a map,say mp.\nWe then keep a temp hashmap for storing all chars\' freq of our current window. When the count
We need to store the freq of all chars of word2 in a map,say mp.\nWe then keep a temp hashmap for storing all chars\' freq of our current window. When the count matches all substrings from current \'end\' pointer to the end of word1 are valid. Hence, add that to the answer and shrink the window.If the outgoing element is leading to decrement of matched chars count, move out of the loop.\n\nLinear time and space complexity. \n\n# Code\n```cpp []\nclass Solution {\npublic:\n    long long validSubstringCount(string word1, string word2) {\n        unordered_map<char,int> mp;\n        for(char ch:word2){\n            mp[ch]++;\n        }\n\n        int start = 0;\n        int end = 0;\n\n        long long ans = 0;\n\n        int count = 0;\n        unordered_map<char,int> temp;\n\n        while(end < word1.length()){\n            if(mp.find(word1[end]) != mp.end()){\n                // cout << "at" << start << " " << end << endl;\n                temp[word1[end]]++;\n                if(temp[word1[end]] <= mp[word1[end]]){\n                    count++;\n                }\n            }\n\n            while(count == word2.size()){\n                ans++;\n                ans += (word1.length()-(end+1)); \n                //current window macthes, then all substring from end to word1.length() also are valid substrings\n                // cout << start << " " << end << endl;\n\n                // cout << word1.length()-(end) << " " << start << " " << end << endl;\n                if(temp.find(word1[start]) != temp.end()){\n                    // mp[word1[start]]++;\n                    temp[word1[start]]--;\n                    if(temp[word1[start]] < mp[word1[start]]){\n                        count--;\n                    }\n                }\n                start++;\n            }\n\n            end++;\n        }   \n\n        return ans;\n    }\n};\n```
['Hash Table', 'Sliding Window', 'C++']