C++ || Easy || Binary Search || Prefix Frequency Table
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem involves finding the number of valid substrings in word1 that satisfy certa
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem involves finding the number of valid substrings in word1 that satisfy certain frequency requirements based on word2. Specifically, for any substring in word1, the frequency of each character in the substring should be greater than or equal to the frequency of the corresponding character in word2.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n**1.Frequency Array for word2:**\nWe first compute the frequency of each character in word2. This frequency array will be used to compare the character frequencies of substrings in word1.\n\n**2.Prefix Frequency Table for word1:**\nFor efficient computation of character frequencies over any substring of word1, we build a prefix frequency table. This table allows us to calculate the frequency of any character in any substring of word1 in constant time.\n\n**3.Binary Search for Valid Substring:**\nFor each starting index i in word1, we perform a binary search to find the smallest valid ending index mid. For the substring from index i to mid, we check if the frequency of each character meets or exceeds the frequency in word2.\n\n- If the current substring satisfies the condition, we try to find a smaller valid ending index to minimize the substring.\n- If it doesn\'t satisfy the condition, we move to larger substrings by increasing the ending index.\n- After determining the smallest valid mid, all substrings from i to the valid indices (mid to n-1) are counted.\n\n**4.Result:**\nWe count and accumulate all valid substrings starting from each index in word1.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nThe overall time complexity is O(n * (log n + 26)) \u2248 O(n * log n), where n is the length of word1.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nThe space used for the frequency array of word2 is O(26).\nThe prefix frequency table for word1 requires O(n * 26) space.\nThus, the total space complexity is O(n * 26) \u2248 O(n).\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    long long validSubstringCount(string word1, string word2) {\n        int n = word1.size();\n        int m = word2.size();\n\n        // Frequency array for word2\n        vector<int> freq(26, 0);\n        for (auto ch : word2) {\n            freq[ch - \'a\']++;\n        }\n        \n        // Frequency table for word1\n        vector<vector<int>> freqTable(26, vector<int>(n, 0));\n        for (int j = 0; j < n; j++) {\n            int ch = word1[j] - \'a\';\n            if (j > 0) {\n                for (int k = 0; k < 26; k++) {\n                    freqTable[k][j] = freqTable[k][j-1];\n                }\n            }\n            freqTable[ch][j]++;\n        }\n\n        long long ans = 0;\n        \n        // Iterate over each starting index in word1\n        for (int i = 0; i < n; i++) {\n            int l = i, r = n - 1, index = -1;\n            \n            // Binary search for the smallest valid ending index\n            while (l <= r) {\n                int mid = l + (r - l) / 2;\n                bool flag = true;\n                \n                // Check if the substring from i to mid satisfies the frequency requirement\n                for (int j = 0; j < 26; j++) {\n                    int currFreq = freqTable[j][mid];\n                    \n                    // If i > 0, subtract the frequencies from the prefix sum up to i-1\n                    if (i > 0) {\n                        currFreq -= freqTable[j][i - 1];\n                    }\n                    \n                    // Check if the current character\'s frequency in the range is valid\n                    if (freq[j] > currFreq) {\n                        flag = false;\n                        break;\n                    }\n                }\n                \n                if (flag) {\n                    index = mid;\n                    r = mid - 1; // Try to find a smaller valid index\n                } else {\n                    l = mid + 1;\n                }\n            }\n\n            // Count all valid substrings starting from i\n            if (index != -1) {\n                ans += (n - index);\n            }\n        }\n\n        return ans;\n    }\n};\n\n```
['Hash Table', 'Binary Search', 'Prefix Sum', 'C++']