Easy C++ Solution | Binary Search | Prefix Sum | Beats 100 💯✅
Intuition and Approach\n\nThe goal is to find the longest substring of equal length in s and t such that the sum of the absolute differences of corresponding ch
## Intuition and Approach\n\nThe goal is to find the longest substring of equal length in `s` and `t` such that the sum of the absolute differences of corresponding characters in this substring is less than or equal to `cost`.\n\n### Steps:\n1. **Precompute the Prefix Sum Array**: Compute a prefix sum array where each element at index `i` represents the cumulative cost of transforming the substring `s[0:i-1]` to `t[0:i-1]`.\n2. **Binary Search**: Use binary search to determine the maximum length of the substring that satisfies the cost constraint.\n3. **Sliding Window Technique**: For each mid value in binary search, use a sliding window to check if there exists a valid substring of that length where the sum of the differences is less than or equal to `cost`.\n\n### Detailed Explanation:\n1. **Prefix Sum Calculation**: This helps in efficiently calculating the sum of differences for any substring.\n2. **Binary Search on Length**: Since we are looking for the maximum length, binary search helps in reducing the search space efficiently.\n3. **Sliding Window within Binary Search**: For each midpoint, use a sliding window to check if a valid substring of that length exists.\n\n### Complexity:\n- **Time Complexity**: `O(n log n)`\n  - Calculating the prefix sum takes `O(n)`.\n  - The binary search runs in `O(log n)` iterations, and in each iteration, the sliding window check takes `O(n)`.\n- **Space Complexity**: `O(n)` for the prefix sum array.\n\n```cpp\nclass Solution {\npublic:\n    bool check(vector<int>& pref, int cost, int mid) {\n        int l = 0, r = mid;\n        while (r < pref.size()) {\n            int sum = pref[r] - pref[l];\n            if (sum <= cost) {\n                return true;\n            }\n            l++;\n            r++;\n        }\n        return false;\n    }\n\n    int equalSubstring(string s, string t, int cost) {\n        int n = s.size();\n        vector<int> pref(n + 1, 0);\n        for (int i = 1; i <= n; i++) {\n            pref[i] = pref[i - 1] + abs(s[i - 1] - t[i - 1]);\n        }\n\n        int l = 0, h = n;\n        int ans = 0;\n        while (l <= h) {\n            int mid = l + (h - l) / 2;\n            if (check(pref, cost, mid)) {\n                ans = mid;\n                l = mid + 1;\n            } else {\n                h = mid - 1;\n            }\n        }\n        return ans;\n    }\n};\n
['Array', 'Binary Search', 'Prefix Sum', 'C++']