Watch 10 video solutions for Get Equal Substrings Within Budget, a medium level problem involving String, Binary Search, Sliding Window. This walkthrough by NeetCodeIO has 9,625 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given two strings s and t of the same length and an integer maxCost.
You want to change s to t. Changing the ith character of s to ith character of t costs |s[i] - t[i]| (i.e., the absolute difference between the ASCII values of the characters).
Return the maximum length of a substring of s that can be changed to be the same as the corresponding substring of t with a cost less than or equal to maxCost. If there is no substring from s that can be changed to its corresponding substring from t, return 0.
Example 1:
Input: s = "abcd", t = "bcdf", maxCost = 3 Output: 3 Explanation: "abc" of s can change to "bcd". That costs 3, so the maximum length is 3.
Example 2:
Input: s = "abcd", t = "cdef", maxCost = 3 Output: 1 Explanation: Each character in s costs 2 to change to character in t, so the maximum length is 1.
Example 3:
Input: s = "abcd", t = "acde", maxCost = 0 Output: 1 Explanation: You cannot make any change, so the maximum length is 1.
Constraints:
1 <= s.length <= 105t.length == s.length0 <= maxCost <= 106s and t consist of only lowercase English letters.Problem Overview: You are given two equal-length strings s and t and an integer maxCost. Changing s[i] to t[i] costs abs(s[i] - t[i]). The goal is to find the maximum length substring you can convert without the total cost exceeding maxCost.
Approach 1: Sliding Window (O(n) time, O(1) space)
The optimal solution uses the sliding window technique. Treat the cost of transforming each character as a running sum while expanding a window with two pointers. Move the right pointer forward and add the cost abs(s[i] - t[i]). If the total cost exceeds maxCost, shrink the window from the left and subtract those costs until the budget is valid again. At every step, update the maximum window length. Each character enters and leaves the window at most once, giving O(n) time complexity and O(1) extra space. This works because substring costs are additive and the constraint only cares about the total within the current window.
Approach 2: Prefix Sum with Binary Search (O(n log n) time, O(n) space)
This approach precomputes the cost difference between s[i] and t[i] and stores cumulative values in a prefix array. Using prefix sums, the cost of any substring [l, r] becomes prefix[r+1] - prefix[l]. For each starting index, perform a binary search to find the farthest ending index whose cost stays within maxCost. This reduces repeated summation and leverages the monotonic nature of prefix sums. The outer loop runs n times and each search takes O(log n), resulting in O(n log n) time and O(n) space. It’s useful when you want a more general framework for cost queries across many substrings.
Recommended for interviews: The sliding window approach is the expected solution. Interviewers want to see that you recognize the problem as a classic variable-length window where the constraint is a running sum bounded by a budget. Demonstrating the prefix-sum + binary-search approach still shows solid problem solving, but the O(n) sliding window solution highlights stronger algorithmic intuition.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window | O(n) | O(1) | Best choice for contiguous substring problems with a running constraint like cost or sum |
| Prefix Sum + Binary Search | O(n log n) | O(n) | Useful when prefix sums are already available or when answering multiple substring cost queries |