Get Equal Substrings Within Budget
MedPrompt
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 <= 106sandtconsist of only lowercase English letters.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach systematically checks every possible substring. For each substring, it calculates the total cost to transform the characters from string s to the corresponding characters in string t. If the calculated cost is within the maxCost budget, it updates the maximum length found so far.
Algorithm
- Create an integer array
costDiffsof the same length ass. - Iterate from
i = 0tos.length() - 1and populatecostDiffs[i] = Math.abs(s.charAt(i) - t.charAt(i)). - Initialize
maxLength = 0. - Iterate with a
startpointer from0tos.length() - 1.- Initialize
currentCost = 0. - Iterate with an
endpointer fromstarttos.length() - 1.- Add
costDiffs[end]tocurrentCost. - If
currentCost <= maxCost, it's a valid substring. UpdatemaxLength = Math.max(maxLength, end - start + 1). - Else, the cost is too high. Break the inner loop since adding more characters will only increase the cost.
- Add
- Initialize
- Return
maxLength.
Walkthrough
First, we can simplify the problem by thinking about an array of costs. Let's define cost[i] = |s[i] - t[i]|. The problem is now equivalent to finding the longest contiguous subarray in this cost array whose sum does not exceed maxCost.
The brute-force method involves using two nested loops to define all possible subarrays. The outer loop sets the starting index (i) of the subarray, and the inner loop sets the ending index (j). For each subarray from i to j, we calculate its sum. To do this efficiently, we maintain a running sum (currentCost) in the inner loop. If currentCost is within the maxCost budget, the current subarray is valid, and we update our maxLength with its length (j - i + 1). If currentCost exceeds maxCost, we can immediately stop extending the current subarray (break the inner loop) because any longer subarray starting at i will also exceed the budget.
class Solution { public int equalSubstring(String s, String t, int maxCost) { int n = s.length(); int maxLength = 0; for (int i = 0; i < n; i++) { int currentCost = 0; for (int j = i; j < n; j++) { currentCost += Math.abs(s.charAt(j) - t.charAt(j)); if (currentCost <= maxCost) { maxLength = Math.max(maxLength, j - i + 1); } else { // Pruning: if cost exceeds, no need to extend this substring further break; } } } return maxLength; }}Complexity
Time
O(n^2), where n is the length of the strings. The two nested loops result in a quadratic number of operations as we check almost all possible substrings.
Space
O(1), as we are not using any extra space that scales with the input size. The cost is calculated on the fly.
Trade-offs
Pros
Simple to understand and implement.
Correct for all inputs, though slow.
Cons
Highly inefficient for large inputs due to its quadratic time complexity.
Will likely result in a 'Time Limit Exceeded' (TLE) error on competitive programming platforms for the given constraints.
This approach uses binary search to find the maximum possible length. The key observation is that if we can afford to change a substring of length k, we can certainly afford to change any substring of a shorter length. This monotonic property allows us to binary search on the answer (the length of the substring).
Algorithm
- Define a search range for the length,
low = 0andhigh = s.length(). - Initialize
ans = 0. - While
low <= high:- Calculate
mid = low + (high - low) / 2. - Call a helper function
isPossible(mid, s, t, maxCost)to check if a substring of lengthmidis possible. - If
isPossiblereturnstrue:- Store
midas a potential answer:ans = mid. - Try for a larger length:
low = mid + 1.
- Store
- Else:
midis too large, try for a smaller length:high = mid - 1.
- Calculate
- Return
ans.
isPossible(k, s, t, maxCost) function:
- Use a sliding window of fixed size
kto check if any subarray of costs has a sum<= maxCost. - Calculate the cost of the first window of size
k. - If the cost is
<= maxCost, returntrue. - Iterate from
i = ktos.length() - 1:- Update the window cost by adding the new element's cost and subtracting the old element's cost.
- If the new cost is
<= maxCost, returntrue.
- If the loop completes, return
false.
Walkthrough
We can binary search for the maximum valid length, which can range from 0 to n. For a given length k (our mid in the binary search), we need a way to efficiently check if there exists any substring of length k whose transformation cost is within maxCost.
To perform this check, we can use a sliding window of fixed size k. We first calculate the cost of the initial window of k characters. If it's within the budget, we've found that length k is possible. If not, we slide the window one position to the right. This is done efficiently by subtracting the cost of the character leaving the window and adding the cost of the character entering. We repeat this until we either find a valid window or exhaust all possibilities. This check takes O(n) time.
The binary search then proceeds as follows: if a length k is possible, we try for a longer length by searching in the upper half (low = mid + 1). If length k is not possible, we must search for a shorter length in the lower half (high = mid - 1).
class Solution { public int equalSubstring(String s, String t, int maxCost) { int n = s.length(); int[] costDiffs = new int[n]; for (int i = 0; i < n; i++) { costDiffs[i] = Math.abs(s.charAt(i) - t.charAt(i)); } int low = 0, high = n, ans = 0; while (low <= high) { int mid = low + (high - low) / 2; if (isPossible(mid, costDiffs, maxCost)) { ans = mid; low = mid + 1; } else { high = mid - 1; } } return ans; } private boolean isPossible(int k, int[] costDiffs, int maxCost) { if (k == 0) return true; long currentCost = 0; int n = costDiffs.length; for (int i = 0; i < k; i++) { currentCost += costDiffs[i]; } if (currentCost <= maxCost) return true; for (int i = k; i < n; i++) { currentCost += costDiffs[i] - costDiffs[i - k]; if (currentCost <= maxCost) return true; } return false; }}Complexity
Time
O(n log n). The binary search performs O(log n) iterations. In each iteration, the `isPossible` check takes O(n) time.
Space
O(n) to store the `costDiffs` array for the check function. This could be avoided by passing `s` and `t` and recalculating costs, but storing them is cleaner.
Trade-offs
Pros
Significantly more efficient than the brute-force approach.
A standard and useful pattern for problems involving finding a maximum/minimum value that satisfies a condition.
Cons
More complex to implement than the brute-force approach.
Not as efficient as the optimal sliding window approach.
This is the most efficient approach for this problem. It leverages the sliding window technique to find the longest subarray with a sum less than or equal to maxCost in a single pass. The problem of finding the longest substring with a certain property is a classic use case for the sliding window pattern.
Algorithm
- Initialize
left = 0,currentCost = 0, andmaxLength = 0. - Iterate with a
rightpointer from0tos.length() - 1.- Calculate the cost for the character at
rightand add it tocurrentCost. - While
currentCost > maxCost:- Subtract the cost of the character at
leftfromcurrentCost. - Increment
leftto shrink the window from the left.
- Subtract the cost of the character at
- The current window
[left, right]is now valid. UpdatemaxLength = Math.max(maxLength, right - left + 1).
- Calculate the cost for the character at
- After the loop, return
maxLength.
Walkthrough
The core idea is to maintain a "window" of the substring, represented by a left and a right pointer. The right pointer always moves forward to expand the window, and the left pointer moves forward only when needed to shrink the window.
We iterate through the string with the right pointer from left to right. At each step, we add the cost of the new character |s[right] - t[right]| to a running total, currentCost.
After adding the new cost, we check if currentCost has exceeded maxCost. If it has, our current window is invalid. To make it valid again, we must shrink it from the left. We do this by moving the left pointer to the right and subtracting the cost of the character at the left index from currentCost. We repeat this shrinking process in a while loop until currentCost is back within the budget.
After the while loop, the window [left, right] is guaranteed to be valid. Its length is right - left + 1. We compare this length with our maxLength and update it if the current window is longer. Since both left and right pointers only move forward, each character's cost is added and subtracted at most once, leading to a linear time complexity.
class Solution { public int equalSubstring(String s, String t, int maxCost) { int n = s.length(); int left = 0; int currentCost = 0; int maxLength = 0; for (int right = 0; right < n; right++) { currentCost += Math.abs(s.charAt(right) - t.charAt(right)); while (currentCost > maxCost) { currentCost -= Math.abs(s.charAt(left) - t.charAt(left)); left++; } maxLength = Math.max(maxLength, right - left + 1); } return maxLength; }}Complexity
Time
O(n), where n is the length of the strings. Both the `left` and `right` pointers traverse the string at most once, making it a single-pass solution.
Space
O(1). We only use a few variables to keep track of the window pointers, current cost, and max length, which does not depend on the input size.
Trade-offs
Pros
Optimal time complexity of O(n).
Optimal space complexity of O(1).
Elegant and efficient solution for this type of problem.
Cons
Might be slightly less intuitive to come up with than the brute-force approach for beginners.
Solutions
Solution
class Solution {private int maxCost;private int[] f;private int n;public int equalSubstring(String s, String t, int maxCost) { n = s.length(); f = new int[n + 1]; this.maxCost = maxCost; for (int i = 0; i < n; ++i) { int x = Math.abs(s.charAt(i) - t.charAt(i)); f[i + 1] = f[i] + x; } int l = 0, r = n; while (l < r) { int mid = (l + r + 1) >>> 1; if (check(mid)) { l = mid; } else { r = mid - 1; } } return l; }private boolean check(int x) { for (int i = 0; i + x - 1 < n; ++i) { int j = i + x - 1; if (f[j + 1] - f[i] <= maxCost) { return true; } } return false; }}class Solution {public: int equalSubstring(string s, string t, int maxCost) { int n = s.size(); int f[n + 1]; f[0] = 0; for (int i = 0; i < n; ++i) { f[i + 1] = f[i] + abs(s[i] - t[i]); } auto check = [&](int x) -> bool { for (int i = 0; i + x - 1 < n; ++i) { int j = i + x - 1; if (f[j + 1] - f[i] <= maxCost) { return true; } } return false; }; int l = 0, r = n; while (l < r) { int mid = (l + r + 1) >> 1; if (check(mid)) { l = mid; } else { r = mid - 1; } } return l; }};class Solution: def equalSubstring(self, s: str, t: str, maxCost: int) -> int: def check(x): for i in range(n): j = i + mid - 1 if j < n and f[j + 1] - f[i] <= maxCost: return True return False n = len(s) f = list(accumulate((abs(ord(a) - ord(b)) for a, b in zip(s, t)), initial=0)) l, r = 0, n while l < r: mid = (l + r + 1) >> 1 if check(mid): l = mid else: r = mid - 1 return lVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.