Get Equal Substrings Within Budget — Medium Problem & Solution

s and t have the same length. Changing s[i] into t[i] costs |s[i] - t[i]| in ASCII.

Difficulty: Medium
Topics: Strings, Binary Search, Sliding Window, Prefix Sum
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 <= 100000
0 <= maxCost <= 1000000
s and t consist of lowercase English letters.

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

maxCost can 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 abs gives negative costs and breaks the monotonicity.
The total reaches 10^5 · 25, well inside int.

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 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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue