[C++] Binary Search the Maximum Length
Intuition\n Describe your first thoughts on how to solve this problem. \n- Define a boolean function check(length) that can check if there exists a substring wi
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- Define a boolean function `check(length)` that can check if there exists a substring with `length` meets the condition\n- The `check(length)` is a function like this:\n  - `f(0) = true`, `f(1) = true`, ... `f(x) = true`, `f(x + 1) = false`, ...\n- We can find the `x` using the binary search\n  - `f(x)` is the right-most true value\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- calculate the prefix sum to get the cost of `s.substr(i, length)`\n- binary search the maximum length\n  - check if there exists a substring meets the condition\n\n# Complexity\n- Time complexity: $$O(n\\times{\\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```\nclass Solution {\npublic:\n    // time/space: O(nlogn)/O(n)\n    int equalSubstring(string s, string t, int maxCost) {\n        // calculate the prefix sum to get the cost of `s.substr(i, length)`\n        int n = s.size();\n        vector<int> prefix(n + 1, 0);\n        for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + abs(s[i] - t[i]);\n\n        // binary search the maximum length\n        int l = 0, r = n;\n        while (l < r) {\n            int m = l + (r - l + 1) / 2;\n            if (check(n, prefix, maxCost, m)) l = m;\n            else r = m - 1;\n        }\n        return l;\n    }\nprivate:\n    // check if there exists a substring meets the condition\n    bool check(int n, vector<int>& prefix, int maxCost, int length) {\n        for (int i = 0; (i + length) <= n; i++) {\n            int cost = prefix[i + length] - prefix[i];\n            if (cost <= maxCost) return true;\n        }\n        return false;\n    }\n};\n```
['C++']