Get Equal Substrings Within Budget

1. Define the problem

Get Equal Substrings Within Budget

You are given two strings s and t of the same length and an integer maxCost. The cost of changing one character of s into the matching character of t is the absolute difference between their character codes. Return the maximum length of a substring of s you can convert to match t without the total cost exceeding maxCost . Grow a window on the right adding its conversion cost, then shrink from the left whenever the total cost goes over budget.

Constraints

1 ≤ s.length == t.length ≤ 10⁵
0 ≤ maxCost ≤ 10⁶
s and t consist of only lowercase English letters

Example

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

Output3

Explanation Changing "abc" to "bcd" costs 1 + 1 + 1 = 3, within budget; including the final d pushes the cost to 5.

2. Know the words first

In plain terms

Character code: The number a computer uses to represent a character internally — 'a' is 97 and 'b' is 98, so the cost to change one into the other is 1.

3. Visualize the solution

Shrink left whenever the cost exceeds the budget

0a/b

1b/c

2c/d

3d/f

Statusvalid

Costs 1+1+1=3 <= 3; best = 3.

What happens in this step

s="abcd", t="bcdf" — per-char cost = |charCode(s[i]) - charCode(t[i])|
  index 0: |a-b| = 1
  index 1: |b-c| = 1
  index 2: |c-d| = 1
  running cost = 1+1+1 = 3 <= maxCost=3 → valid
  best = max(0, 2-0+1) = 3

Step 1 of 3

Steps to visualize

Grow right and add the cost of changing that character into the running total.
While the total cost exceeds maxCost, subtract the leftmost cost and advance left.
After each adjustment, the window represents a substring convertible within budget.
Track the longest such window seen.
Continue until right reaches the end of the string.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Shrink left whenever the cost exceeds the budget

0a/b

1b/c

2c/d

3d/f

Statusvalid

Costs 1+1+1=3 <= 3; best = 3.

What happens in this step

s="abcd", t="bcdf" — per-char cost = |charCode(s[i]) - charCode(t[i])|
  index 0: |a-b| = 1
  index 1: |b-c| = 1
  index 2: |c-d| = 1
  running cost = 1+1+1 = 3 <= maxCost=3 → valid
  best = max(0, 2-0+1) = 3

Step 1 of 3

5. Solution

Solution

solution.tsTypeScript

function equalSubstring(s, t, maxCost) {
  let left = 0;
  let cost = 0;
  let 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;
}

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

6. Test cases

Test cases

Input	Expected	Covers
`s = "abcd", t = "bcdf", maxCost = 3`	`3`	Docstring example
`s = "aaaa", t = "bbbb", maxCost = 0`	`0`	maxCost = 0 with no already-equal characters
`s = "abcd", t = "bcde", maxCost = 100`	`4`	Budget large enough to cover everything
`s = "a", t = "z", maxCost = 1`	`0`	A single character's own cost exceeds the budget
`s = "aabb", t = "aabb", maxCost = 0`	`4`	Every character already matches
`s = "a", t = "a", maxCost = 0`	`1`	Single already-equal character
`s = "krrgw", t = "zjxss", maxCost = 19`	`2`	Multiple shrink cycles across the window

Get Equal Substrings Within Budget