Get Equal Substrings Within Budget — Variable Sliding Window on Cost (LC 1208)

Problem Statement#

LeetCode 1208 — Get Equal Substrings Within Budget (Medium)

You are given two equal-length strings s and t and an integer maxCost. Changing s[i] to t[i] costs |s[i] - t[i]| (absolute ASCII difference). Return the maximum length of a substring of s that can be changed to the corresponding substring of t within maxCost.

Constraints:

• 1 <= s.length <= 10^5
• t.length == s.length
• 0 <= maxCost <= 10^6
• s and t consist of only lowercase English letters

Input:  s = "abcd", t = "bcdf", maxCost = 3
Output: 3

Input:  s = "abcd", t = "cdef", maxCost = 3
Output: 1

Why This Problem Matters#

This problem is a direct application of the variable-size sliding window pattern. The challenge is maintaining a window whose total transformation cost stays within a budget while maximising the window size.

The pattern generalises to many real-world contexts: network packet buffering (how many packets can be in flight within buffer limits?), text diffing (longest common prefix alignable within an edit budget?), and NLP preprocessing (largest text chunk transformable within computational cost limits?). Mastering the "expand right, shrink left" dynamic is essential for LC 3, LC 76, LC 424, and dozens of similar problems at top tech companies.

The Core Insight#

Compute cost[i] = |ord(s[i]) - ord(t[i])| inline as you go. The problem reduces to: find the maximum-length subarray with sum of costs <= maxCost.

Variable sliding window:

• Expand right one step, adding the cost of position right
• While running sum exceeds maxCost, shrink from left
• After adjusting, window [left, right] is valid; record right - left + 1

Costs are non-negative, so adding characters to the right can only increase cost. When the window is invalid, removing characters from the left is the only fix. Two-pointer invariant guarantees the window at each step is the longest valid window ending at right.

Visual Dry Run#

Input: s = "abcd", t = "bcdf", maxCost = 3, cost array: [1, 1, 1, 2]

Answer: 3

Solution (Optimal)#

def equalSubstring(s: str, t: str, maxCost: int) -> int:
    left = 0
    running_cost = 0
    ans = 0
 
    for right in range(len(s)):
        running_cost += abs(ord(s[right]) - ord(t[right]))
 
        while running_cost > maxCost:
            running_cost -= abs(ord(s[left]) - ord(t[left]))
            left += 1
 
        ans = max(ans, right - left + 1)
 
    return ans

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

Time: O(n) — each pointer moves at most n steps; amortized O(1) per step Space: O(1) — cost computed inline, no auxiliary array

Common Mistakes#

• Using a fixed-size window — this problem needs variable size because the budget constraint determines the valid window length
• Forgetting to shrink when cost exceeds maxCost — running cost grows unboundedly and invalid windows are recorded
• Using ord() incorrectly in Python — abs(s[i] - t[i]) raises TypeError; must use abs(ord(s[i]) - ord(t[i]))
• Shrinking past validity — only shrink until running_cost <= maxCost, not to the smallest possible window
• Recording ans before the shrink loop — compute window length after the while-loop completes

Interview Tips#

• The while-loop inside the for-loop is O(n) amortized, not O(n^2) — left moves forward at most n times total
• maxCost = 0 is handled naturally: any position with cost 0 extends the window; cost > 0 forces immediate shrink
• Computing cost inline (abs(ord(s[right]) - ord(t[right]))) avoids a separate preprocessing pass

Follow-up Questions#

• Cost is character change count (not ASCII distance): change cost to 0 if s[i] == t[i] else 1; same sliding window
• Return the actual substring: track start = left when ans updates; return s[start : start + ans]
• Minimum cost to transform a window of length exactly L: fix window size to L, slide with prefix sums
• Binary search alternative: binary search on window length L, check with prefix sums — O(n log n) vs O(n) sliding window

Key Takeaways#

• Variable sliding window: expand right unconditionally, shrink left while cost exceeds budget, track maximum valid window
• Non-negative costs guarantee that shrinking from the left always reduces the window cost — this is the key invariant
• Compute cost inline as abs(ord(s[right]) - ord(t[right])) — no separate cost array needed
• The while-loop for shrinking is amortized O(1) per step; total time O(n), space O(1)
• This "expand right, shrink left" template is the canonical variable window pattern — memorise it and apply to any "max window under budget" problem