From Brute Force to Elegance: Counting Rearranged Substrings Efficiently🔥
A Better Approach:\n\nWe can optimize the solution by using the following strategy:\n\nObservation:\n\nWe need to count the number of substrings where the count
**A Better Approach:**\n\nWe can optimize the solution by using the following strategy:\n\n**Observation:**\n\nWe need to count the number of substrings where the counts of each character are at least those in target. This means for every character in target, the substring must contain that character at least as many times.\n**\nAlgorithm Overview:**\n\n**Precompute Prefix Sums:**\n\nFor each character \'a\' to \'z\', compute the prefix sums in s. This allows us to get the count of any character in any substring in O(1) time.\n\n**Binary Search for Each Starting Index:**\n\nFor each starting index l in s, we can perform a binary search to find the smallest ending index r such that the substring s[l...r] covers all character counts in target.\n\n**Counting Valid Substrings:**\n\nOnce we find the minimal r for a given l, all substrings s[l...r\'], r\' >= r will be valid. So, the number of valid substrings starting at l is n - r, where n is the length of s.\n\n**Detailed Steps:**\n\nInitialize Data Structures:\n\nCreate a frequency array targetCount[26] for target.\nCompute prefix sums prefixSum[26][n + 1] for each character in s.\nProcessing Each Starting Index:\n\nFor l from 0 to n - 1:\n\nCheck Feasibility:\n\nIf the remaining characters from l to n - 1 cannot cover target, we can break early.\n\nBinary Search:\n\nInitialize lo = l, hi = n - 1, and ans = n.\nWhile lo <= hi:\nCompute mid = (lo + hi) / 2.\nFor each character c in target:\nCalculate the count of c in s[l...mid] using prefix sums.\nIf this count is less than required, break and move lo to mid + 1.\nIf all character counts are sufficient, update ans = mid and move hi to mid - 1.\nThe number of valid substrings starting at l is n - ans.\nAggregate the Result:\n\nSum up the counts from step 2 for all l to get the final answer.\n\n\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    long long validSubstringCount(string s, string target) {\n        int n = s.size();\n        vector<int> targetCount(26, 0);\n        for (char c : target) targetCount[c - \'a\']++;\n\n        // Compute prefix sums for each character\n        vector<vector<int>> prefixSum(26, vector<int>(n + 1, 0));\n        for (int i = 0; i < n; i++) {\n            for (int c = 0; c < 26; c++) {\n                prefixSum[c][i + 1] = prefixSum[c][i];\n            }\n            prefixSum[s[i] - \'a\'][i + 1]++;\n        }\n\n        long long total = 0;\n        for (int l = 0; l < n; l++) {\n            int lo = l, hi = n - 1, ans = n;\n            while (lo <= hi) {\n                int mid = lo + (hi - lo) / 2;\n                bool valid = true;\n                for (int c = 0; c < 26; c++) {\n                    int countInWindow = prefixSum[c][mid + 1] - prefixSum[c][l];\n                    if (countInWindow < targetCount[c]) {\n                        valid = false;\n                        break;\n                    }\n                }\n                if (valid) {\n                    ans = mid;\n                    hi = mid - 1;\n                } else {\n                    lo = mid + 1;\n                }\n            }\n            if (ans < n) {\n                total += n - ans;\n            }\n        }\n        return total;\n    }\n};\n\n```
['C++']