Get Equal Substrings Within Budget

medium sliding window string two pointers

Problem

You are given two equal-length strings s and t. Changing the i-th character of s to the i-th character of t costs |s[i] − t[i]| (the absolute difference of their ASCII values). You have a budget maxCost. Return the maximum length of a substring of s that can be changed to the matching substring of t with a total cost no greater than maxCost.

Inputs = "abcd", t = "bcdf", maxCost = 3

Output3

Each position costs |a−b|=1, |b−c|=1, |c−d|=1, |d−f|=2. The first three positions cost 1+1+1 = 3 ≤ 3, giving length 3.

maxCost

def equal_substring(s, t, max_cost):
    left = 0
    cost = 0
    best = 0
    for right in range(len(s)):
        cost += abs(ord(s[right]) - ord(t[right]))
        while cost > max_cost:
            cost -= abs(ord(s[left]) - ord(t[left]))
            left += 1
        best = max(best, right - left + 1)
    return best

function equalSubstring(s, t, maxCost) {
  let left = 0, cost = 0, best = 0;
  for (let right = 0; right < s.length; right++) {
    cost += Math.abs(s.charCodeAt(right) - t.charCodeAt(right));
    while (cost > maxCost) {
      cost -= Math.abs(s.charCodeAt(left) - t.charCodeAt(left));
      left++;
    }
    best = Math.max(best, right - left + 1);
  }
  return best;
}

class Solution {
    public int equalSubstring(String s, String t, int maxCost) {
        int left = 0, cost = 0, best = 0;
        for (int right = 0; right < s.length(); right++) {
            cost += Math.abs(s.charAt(right) - t.charAt(right));
            while (cost > maxCost) {
                cost -= Math.abs(s.charAt(left) - t.charAt(left));
                left++;
            }
            best = Math.max(best, right - left + 1);
        }
        return best;
    }
}

int equalSubstring(string s, string t, int maxCost) {
    int left = 0, cost = 0, best = 0;
    for (int right = 0; right < (int)s.size(); right++) {
        cost += abs(s[right] - t[right]);
        while (cost > maxCost) {
            cost -= abs(s[left] - t[left]);
            left++;
        }
        best = max(best, right - left + 1);
    }
    return best;
}

Explanation

Each position has a fixed conversion cost |s[i] - t[i]| (the difference of the two letters' ASCII codes). We want the longest run of positions whose total cost stays within maxCost, which is a classic sliding-window problem.

We expand the right edge, adding cost for the new position. If the window's total cost goes over maxCost, we shrink from the left, subtracting those positions' costs until we are back within budget.

After each adjustment the window is affordable, so we record its length right - left + 1 in best. This works because costs are never negative, so dropping left elements can only lower the total.

Example: s = "abcd", t = "bcdf", maxCost = 3. The per-position costs are 1, 1, 1, 2. The first three sum to 3, exactly the budget, giving length 3; adding the 2 would exceed it, so the answer is 3.

Each index is added and removed at most once, so the entire scan is linear.

Time: O(n) Space: O(1)