Simple Clean Solution Using Binary Search
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O(n log n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n)\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        int m=word1.length();\n        int n=word2.length();\n        vector<vector<int>> prefixFreq(m+1,vector<int>(26));\n        for(int i=0;i<m;i++){\n            prefixFreq[i+1]=prefixFreq[i];\n            prefixFreq[i+1][word1[i]-\'a\']++;\n        }\n\n        vector<int> toSearch(26);\n        for(int j=0;j<n;j++){\n            toSearch[word2[j]-\'a\']++;\n        }\n\n        long long ans=0;\n        for(int i=0;i<m;i++){\n            ans+=m-binarySearch(toSearch,i,prefixFreq,m);\n            toSearch[word1[i]-\'a\']++;\n        }\n        return ans;\n    }\n\n    int binarySearch(vector<int>& toSearch,int start,vector<vector<int>>& prefix,int m){\n        int end = prefix.size()-2;\n        int ans=m;\n        while(start<=end){\n            int mid = (start+end)/2;\n            if(isValid(prefix[mid+1],toSearch)){\n                ans=mid;\n                end=mid-1;\n            } else {\n                start=mid+1;\n            }\n        }\n        return ans;\n    }\n\n    bool isValid(vector<int>& prefix,vector<int>& toSearch){\n        for(int i=0;i<26;i++){\n            if(prefix[i]<toSearch[i]){\n                return false;\n            }\n        }\n        return true;\n    }\n};\n\n/*\n\n    a   b   c   a   b   c\n\na   1   1   1   2   2   2\nb   0   1   1   1   2   2 \nc   0   0   1   1   1   2\n\n\n*/\n```
['Hash Table', 'Binary Search', 'C++']