C++ | Binary Search | PrefixSums for freq
Approach\n- Prefix Sum Array: Build a 2D prefix sum array prefixSums for word1, where prefixSums[i][j] stores the frequency of the i-th letter (\'a\' to \'z\') 
# Approach\n- **Prefix Sum Array**: Build a 2D prefix sum array prefixSums for word1, where prefixSums[i][j] stores the frequency of the i-th letter (\'a\' to \'z\') from the start of word1 up to index j.\n\n- **Binary Search for Valid Substring**: For each starting index `i` in word1, perform a binary search to find the smallest ending index k such that the substring word1[i:k] contains all characters in at least the frequency as word2(valid).\n\n- **Final Count**: Substrings after the idx k will be valid only add (n - k) to your ans. (Hence reducing the iterations)\n\n# Code\n```cpp\nclass Solution {\n    vector<vector<int>> prefixSums;\n    int n;\n    unordered_map<int, int> freqWord_2;\n\n    int binarySearch(int s) {\n        int start = s;\n        int end = n;\n        \n        while (start < end) {\n            int mid = start + (end - start) / 2;\n            bool valid = true;\n\n            for (int i = 0; i < 26; i++) {\n                int f = prefixSums[i][mid] - (s > 0 ? prefixSums[i][s - 1] : 0);\n                if (f < freqWord_2[i]) {\n                    valid = false;\n                    break;\n                }\n            }\n\n            if (valid) {\n                end = mid; \n            } else {\n                start = mid + 1;\n            }\n        }\n\n        return start;\n    }\n\npublic:\n    long long validSubstringCount(string word1, string word2) {\n        n = word1.length();\n        prefixSums.resize(26, vector<int>(n, 0));\n\n        for (char ch : word2) {\n            freqWord_2[ch - \'a\']++;\n        }\n\n        prefixSums[word1[0] - \'a\'][0] = 1;\n        for (int i = 1; i < n; i++) {\n            for (int j = 0; j < 26; j++) {\n                prefixSums[j][i] = prefixSums[j][i - 1];\n            }\n            prefixSums[word1[i] - \'a\'][i]++;\n        }\n\n        long long ans = 0;\n\n        for (int i = 0; i < n; i++) {\n            int k = binarySearch(i); \n            ans += (n - k);\n        }\n\n        return ans;\n    }\n};\n```
['C++']