Get Equal Substrings Within Budget — Problem & Solution
Get Equal Substrings Within Budget solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Get Equal Substrings Within Budget is a medium coding problem on strings, binary search and prefix sum, asked in Amazon, Google and Infosys interviews.
- Difficulty: Medium
- Topics: Strings, Binary Search, Prefix Sum, Sliding Window
- Asked at: Amazon, Google, Infosys
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
s and t have the same length. Changing s[i] into t[i] costs |s[i] - t[i]| in ASCII.
With a total budget of maxCost, return the length of the longest substring of s you can turn into the matching substring of t.
Example 1
Input: s = "codekairo", t = "codekairp", maxCost = 1
Output: 9
Explanation: Only the last character differs, at a cost of 1.
Example 2
Input: s = "abcd", t = "bcdf", maxCost = 3
Output: 3
Explanation: Changing "abc" to "bcd" costs 3.
Example 3
Input: s = "abcd", t = "acde", maxCost = 0
Output: 1
Explanation: With no budget, only an already-matching character counts.
Constraints
1 <= s.length == t.length <= 1000000 <= maxCost <= 1000000s and t consist of lowercase English letters.
Hints for Get Equal Substrings Within Budget
Hint 1
Turn the two strings into one array of per-index costs.
Hint 2
The question becomes: the longest subarray whose sum is at most
maxCost.Hint 3
Costs are non-negative, so shrinking a window never raises its sum — a plain two-pointer window works.
How to solve Get Equal Substrings Within Budget
Reduce to a single cost array, then find the longest window whose sum fits the budget. Non-negative costs make the sum monotone in the window's width, which is exactly what a sliding window needs.
Approach
- For each index, the cost is
|s[i] - t[i]|. - Extend the right edge, adding that cost to the running sum.
- While the sum exceeds
maxCost, subtract the left cost and advance the left edge. - Track the longest valid window.
Why it works
Every cost is at least 0, so removing an index can only lower the window's total. For a fixed right edge the valid left edges therefore form a suffix, so the left pointer never moves backwards and the whole scan is linear. With negative costs this would fail and a prefix-sum approach would be needed.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
maxCostcan be 0, where the answer is the longest run of already-equal characters (at least 1 if any index matches, else 1 for a zero-length... in fact 0 when no index matches).- Comparing characters without
absgives negative costs and breaks the monotonicity. - The total reaches
10^5 · 25, well insideint.
Reference solution
Python
def equalSubstring(s: str, t: str, maxCost: int) -> int:
l = 0
cost = 0
best = 0
for r in range(len(s)):
cost += abs(ord(s[r]) - ord(t[r]))
while cost > maxCost:
cost -= abs(ord(s[l]) - ord(t[l]))
l += 1
best = max(best, r - l + 1)
return bestJava
public static int equalSubstring(String s, String t, int maxCost) {
int l = 0, cost = 0, best = 0;
for (int r = 0; r < s.length(); r++) {
cost += Math.abs(s.charAt(r) - t.charAt(r));
while (cost > maxCost) {
cost -= Math.abs(s.charAt(l) - t.charAt(l));
l++;
}
best = Math.max(best, r - l + 1);
}
return best;
}C++
int equalSubstring(string s, string t, int maxCost) {
int l = 0, cost = 0, best = 0;
for (int r = 0; r < (int) s.size(); r++) {
cost += abs(s[r] - t[r]);
while (cost > maxCost) {
cost -= abs(s[l] - t[l]);
l++;
}
best = max(best, r - l + 1);
}
return best;
}JavaScript
var equalSubstring = function(s, t, maxCost) {
var l = 0, cost = 0, best = 0;
for (var r = 0; r < s.length; r++) {
cost += Math.abs(s.charCodeAt(r) - t.charCodeAt(r));
while (cost > maxCost) {
cost -= Math.abs(s.charCodeAt(l) - t.charCodeAt(l));
l++;
}
if (r - l + 1 > best) best = r - l + 1;
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Binary Search