Get Equal Substrings Within Budget
Medium · Sliding Window · String · Sliding Window · Prefix Sum · Binary Search
Problem
You are given two strings s and t of the same length and an integer maxCost. Changing s[i] into t[i] costs |s[i] - t[i]|, the absolute difference of their character codes.
Return the maximum length of a substring of s that can be turned into the substring of t at the same positions for a total cost of at most maxCost. If not even one character can be afforded, return 0.
Examples
Input: s = "abcd", t = "bcdz", maxCost = 3 Output: 3
The first three positions cost 1 each, for a total of 3. The last one would cost 22.
Input: s = "kitten", t = "sitten", maxCost = 0 Output: 5
Positions 1 to 5 already match, so "itten" costs nothing. Position 0 costs 8.
Input: s = "abc", t = "xyz", maxCost = 1 Output: 0
Every position costs 23, more than the budget.
Constraints
- 1 <= len(s) <= 10^5
- len(t) == len(s)
- 0 <= maxCost <= 10^6
- s and t consist of lowercase English letters
Approaches
- Baseline: every start, extend while affordable — time O(n²), space O(1)
Follow-up
What if a change could also cost a negative amount (a refund)? Then a longer window can be cheaper than a shorter one, and the shrink-from-the-left rule is no longer safe: you would need prefix sums and a sorted structure (or a monotonic stack) to find, for each right end, the earliest prefix that keeps the cost within budget.
Related problems
Start free on Cariara · Coding problems · System design studio
