Get Equal Substrings Within Budget

Medium
793.

Get Equal Substrings Within Budget

Get Equal Substrings Within Budget is a medium coding problem on strings, binary search and prefix sum, asked in Amazon, Google and Infosys interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {string} t
 * @param {number} maxCost
 * @return {number}
 */
var equalSubstring = function(s, t, maxCost) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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.

Hints for Get Equal Substrings Within Budget

  1. Hint 1

    Turn the two strings into one array of per-index costs.

  2. Hint 2

    The question becomes: the longest subarray whose sum is at most maxCost.

  3. 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

  1. For each index, the cost is |s[i] - t[i]|.
  2. Extend the right edge, adding that cost to the running sum.
  3. While the sum exceeds maxCost, subtract the left cost and advance the left edge.
  4. 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

Java

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