Binary Search | Beginner friendly approach
Intuition\n Describe your first thoughts on how to solve this problem. \nThe goal of the code is to count the number of valid substrings in s where any rearrang
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe goal of the code is to count the number of valid substrings in s where any rearrangement of the substring can have word2 as a prefix. The given solution uses a combination of prefix sum arrays and binary search to achieve this efficiently.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n**Character Frequency Calculation:**\n\n- Calculate the frequency of each character in word2 and store it in the base vector.\n\n\n\n**Prefix Sum Array for Character Counts:**\n\n- Create a prefix sum array pre where pre[i] stores the cumulative counts of each character from the start of the string s up to the i-th position.\n\n\n**Find Valid Substrings Using Binary Search:**\n\n- For each starting position i in the string s, use binary search to find the shortest ending index idx such that the substring from i to idx contains all characters in word2 with the required frequency.\n\n- Calculate how many substrings can be generated from this range and add it to the result.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(NlogN)$$ \n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(1)$$\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    long long validSubstringCount(string s, string word2) \n    {\n        int n = s.size(), i, j;\n    \n        // Count the frequency of characters in word2\n        vector<int> base(26);\n        for (auto ch : word2)\n        {\n            base[ch - \'a\']++;\n        }\n        \n        // Create a prefix sum array for character frequencies in s\n        vector<vector<int>> pre(n + 1, vector<int>(26, 0));\n        for(i = 0; i < n; i++)\n        {\n            pre[i + 1][s[i] - \'a\']++;\n            for(j = 0; j < 26; j++)\n            {\n                pre[i + 1][j] += pre[i][j];\n            }\n        }\n        \n        long long ans = 0;\n        \n        // Iterate through each starting position in the string\n        for(i = 0; i < n; i++)\n        {\n            int l = i, r = n - 1, idx = 1e9;\n            \n            // Perform binary search to find the minimum valid ending index\n            while(l <= r)\n            {\n                int mid = (l + r) / 2;\n                bool ok = true;\n                \n                // Check if the substring from i to mid satisfies the frequency requirement\n                for(j = 0; j < 26; j++)\n                {\n                    if(base[j] > (pre[mid + 1][j] - pre[i][j]))\n                    {\n                        ok = false;\n                        break;\n                    }\n                }\n                \n                if(ok)\n                {\n                    idx = mid;\n                    r = mid - 1;\n                }\n                else\n                {\n                    l = mid + 1;\n                }\n            }\n            \n            // Count all valid substrings ending at index idx or later\n            if (idx < 1e9)\n            {\n                ans += (n - idx);\n            }\n        }\n        \n        return ans;\n    }\n};\n```
['Binary Search', 'C++']