1208. Get Equal Substrings Within Budget - Explanation

Problem Link



1. Brute Force

Intuition

We want to find the longest substring where the total transformation cost stays within the budget. The transformation cost at each position is the absolute difference between the ASCII values of the corresponding characters. By checking every possible substring and tracking its cost, we can find the maximum valid length.

Algorithm

  1. For each starting index i, try extending the substring to the right.
  2. Maintain a running cost by adding |s[j] - t[j]| for each new character.
  3. If the cost exceeds maxCost, stop extending from this start.
  4. Track the maximum valid substring length found.
  5. Return the maximum length.
class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        n = len(s)
        res = 0

        for i in range(n):
            cur_cost = 0
            for j in range(i, n):
                cur_cost += abs(ord(t[j]) - ord(s[j]))
                if cur_cost > maxCost:
                    break
                res = max(res, j - i + 1)

        return res

Time & Space Complexity

  • Time complexity: O(n2)O(n ^ 2)
  • Space complexity: O(1)O(1)

2. Sliding Window

Intuition

Since we want the longest contiguous substring within a cost budget, a sliding window is ideal. We expand the window by moving the right pointer and shrink it from the left when the cost exceeds the budget. This efficiently explores all valid windows in linear time.

Algorithm

  1. Initialize two pointers l and r at the start, and a running curCost of 0.
  2. Expand the window by moving r and adding |s[r] - t[r]| to curCost.
  3. While curCost exceeds maxCost, shrink the window by subtracting |s[l] - t[l]| and incrementing l.
  4. Update the result with the current window size r - l + 1.
  5. Return the maximum window size found.
class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        curCost = 0
        l = 0
        res = 0

        for r in range(len(s)):
            curCost += abs(ord(s[r]) - ord(t[r]))
            while curCost > maxCost:
                curCost -= abs(ord(s[l]) - ord(t[l]))
                l += 1
            res = max(res, r - l + 1)

        return res

Time & Space Complexity

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

3. Sliding Window (Optimal)

Intuition

We can simplify the sliding window by never shrinking it more than one position at a time. Once we find a valid window of size k, we only care about finding windows of size k+1 or larger. If the current window is invalid, we slide both pointers together, maintaining the window size. The final answer is derived from the position of the left pointer l.

Algorithm

  1. Start with l = 0 and iterate r from 0 to n-1.
  2. Subtract |s[r] - t[r]| from maxCost.
  3. If maxCost goes negative, add back |s[l] - t[l]| and increment l by one.
  4. The window never shrinks below its maximum valid size.
  5. Return n - l as the result.
class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        l = 0
        for r in range(len(s)):
            maxCost -= abs(ord(s[r]) - ord(t[r]))
            if maxCost < 0:
                maxCost += abs(ord(s[l]) - ord(t[l]))
                l += 1
        return len(s) - l

Time & Space Complexity

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

Common Pitfalls

Forgetting to Use Absolute Value for Cost Calculation

When computing the transformation cost between characters, you must use the absolute difference |s[i] - t[i]|. Forgetting to take the absolute value will produce negative costs when t[i] < s[i], leading to incorrect results. Always wrap the difference in abs() or Math.abs().

Shrinking the Window Too Aggressively

In the standard sliding window approach, when the cost exceeds the budget, you should shrink the window from the left one step at a time while updating the running cost. A common mistake is resetting the left pointer to right + 1 or incorrectly jumping the left pointer, which skips valid substrings and produces suboptimal answers.

Returning Window Size Instead of Maximum Length

The problem asks for the maximum length found across all valid windows, not the final window size. Make sure to track and update a separate result variable with max(result, r - l + 1) after each expansion, rather than just returning r - l + 1 at the end of the loop.