Get Equal Substrings Within Budget: Sliding Window Cost Control

LeetCode 1208 Get Equal Substrings Within Budget gives you two strings s and t of the same length, plus an integer maxCost. You can change s[i] to t[i] at a cost of |s[i] - t[i]| (the absolute difference of their ASCII values). Your goal is to find the maximum length of a substring of s that you can convert to the corresponding substring of t without the total cost exceeding maxCost.

For example, given s = "abcd", t = "bcdf", and maxCost = 3, the per-position costs are [1, 1, 1, 2]. The longest substring you can convert is "abc" to "bcd" at cost 1+1+1 = 3. The answer is 3.

If you have worked through Longest Substring Without Repeating Characters or Longest Repeating Character Replacement, you will recognize the sliding window structure here. The twist is that the window constraint is a running cost sum rather than a character frequency condition.

Why this problem matters

This problem teaches you to apply the sliding window pattern to a numeric constraint. Many real-world problems boil down to "find the longest contiguous range where some running total stays within a limit." Network packet windows, time-series analysis, and resource budgeting all follow this shape.

Once you see that the problem reduces to "maximum-length subarray with sum <= maxCost," the sliding window template drops in directly. That reduction step, transforming a string problem into a numeric one, is the key skill this problem drills.

The key insight

The first step is to realize you do not need to think about characters at all. Compute a cost array where cost[i] = |s[i] - t[i]|. Now the problem becomes: find the longest contiguous subarray of cost whose sum is at most maxCost.

This is a classic sliding window setup. You maintain a window [left, right] and a running currentCost that tracks the sum of costs inside the window. Expand right to grow the window. When currentCost exceeds maxCost, shrink from the left by subtracting cost[left] and advancing left.

Because both pointers only move forward, the total work is O(n). You never backtrack, you never recompute sums from scratch. The running total is maintained incrementally: add when expanding, subtract when shrinking.

The solution

def equalSubstring(s, t, maxCost):
    n = len(s)
    left = 0
    current_cost = 0
    best = 0

    for right in range(n):
        current_cost += abs(ord(s[right]) - ord(t[right]))

        while current_cost > maxCost:
            current_cost -= abs(ord(s[left]) - ord(t[left]))
            left += 1

        best = max(best, right - left + 1)

    return best

Here is what each part does:

1. current_cost tracks the sum of |s[i] - t[i]| for every index in the current window.
2. The for loop advances right one position at a time, adding the new position's cost to current_cost.
3. The while loop fires when the budget is exceeded. It subtracts the cost at left and moves left forward until the window is back within budget.
4. After each expansion (and possible shrink), we update best with the current window length.

Visual walkthrough

Notice how the window grows freely when costs are small, then shrinks rapidly when it hits the expensive position at index 3 (cost = 2). The key observation: after shrinking, the algorithm does not restart from the beginning. It picks up right where it left off, which is why the total work stays linear.

Complexity analysis

Time: O(n). The right pointer visits each index once. The left pointer also visits each index at most once. Every element is added to and subtracted from current_cost at most once, giving at most 2n operations total.

Space: O(1). We only store left, current_cost, and best. No auxiliary arrays or data structures are needed since we compute costs on the fly.

Edge cases

• All costs are zero: every character already matches. The answer is n because the entire string is free to "convert."
• maxCost is zero: only positions where s[i] == t[i] (cost zero) can be included. The answer is the longest run of matching characters.
• Single character: the answer is 1 if |s[0] - t[0]| is at most maxCost, otherwise 0.
• maxCost is very large: the budget never runs out. The answer is n because the entire string fits.
• Every position has high cost: if every individual cost exceeds maxCost, the answer is 0 because no single character can be converted.
• Strings of length 1: a minimal edge case that tests the boundary of the loop logic.

The building blocks

1. Transform to a cost array

The first building block is recognizing that character-level differences can be reduced to a numeric array. This "reduce the problem" step appears in many string problems.

cost_i = abs(ord(s[i]) - ord(t[i]))

Once you have a numeric array, you can apply standard array techniques (prefix sums, sliding windows, binary search) without worrying about character logic.

2. Maximum-length subarray with bounded sum

The second building block is the sliding window over a non-negative array with a sum constraint. The window expands greedily and shrinks only when the constraint is violated. This is the same skeleton used in minimum size subarray sum, subarray product less than k, and many other problems.

left = 0
running_sum = 0
for right in range(n):
    running_sum += arr[right]
    while running_sum > limit:
        running_sum -= arr[left]
        left += 1
    best = max(best, right - left + 1)

The non-negative property of the cost values is critical here. It guarantees that shrinking the window always reduces the sum, so the while loop always terminates. If values could be negative, this approach would break and you would need a different technique like a deque or prefix sum with binary search.

From understanding to recall

Reading through this solution once gives you the idea. But when you sit down in an interview next month, you need to reproduce the transform-then-slide approach from memory. Spaced repetition bridges that gap. By revisiting the cost-array reduction and the bounded-sum window template at increasing intervals, you build the muscle memory to assemble them on the fly, even under pressure.

Related posts

• Longest Substring Without Repeating Characters - the classic growing-window problem using a set for duplicate tracking
• Minimum Window Substring - a shrinking-window variant where you minimize length instead of maximizing it
• Minimum Size Subarray Sum - another bounded-sum sliding window, but searching for the shortest subarray