Domain 2MediumMEDIUM

Get Equal Substrings Within Budget

LeetCode problem 1208: Get Equal Substrings Within Budget (medium).

Domain: medium•Updated: 2026-09-10
#Array#Sliding Window

Problem Breakdown

We are given two strings s and t of equal length, along with a budget integer maxCost. Changing the character at index i in s to match t costs the absolute difference between their ASCII values (|ord(s[i]) - ord(t[i])|).

Goal: Find the maximum length of any substring where we can change characters from s to match t within the given budget.

  • Inputs: Two strings s, t (length NN), integer maxCost.
  • Output: Integer representing max valid substring length.
  • Constraints: Length up to 10510^5, costs are non-negative, ASCII values for lowercase English letters only.

Edge Cases & Tricky Parts:

  • If no characters match exactly and every single change exceeds maxCost, the answer should be 0 (though constraints imply valid inputs exist).
  • maxCost can be 0; this implies we can only keep substrings where s[i]==t[i]s[i] == t[i] for all indices in that substring.
  • Large input size (10510^5) requires an O(N) solution, ruling out nested loops or checking every subarray individually.

Intuition

A brute-force approach would check every possible start and end index pair (i,j)(i, j) to calculate the cost of transforming s[i..j]s[i..j] into t[i..j]t[i..j]. This involves iterating through all substrings (O(N2)O(N^2)) and summing costs for each (O(N)O(N)), resulting in O(N3)O(N^3) or optimized to O(N2)O(N^2). Given the constraint of 10510^5, this will time out.

However, notice that cost is always non-negative (absolute difference). This monotonicity suggests a Sliding Window approach:

  1. Expand the window by moving right forward and adding costs.
  2. If the total cost exceeds maxCost, shrink from the left (left) until valid again.
  3. Track the maximum width of any valid window encountered during this process.

This ensures each element is added once and removed at most once, achieving O(N)O(N) time complexity.

Approach

  1. Initialize two pointers left = 0 and right = 0, along with a running variable current_cost.
  2. Iterate through the string using right from 0 to N−1N-1.
  3. Calculate cost for index right: abs(ord(s[right]) - ord(t[right])). Add this to current_cost.
  4. While current_cost > maxCost, subtract the cost of character at left and increment left. This shrinks the window until it is valid again.
  5. Update global maximum length: max_len = right - left + 1. Note that if we shrink past a point where no characters remain, this formula naturally handles empty windows (though logic ensures right >= left).
  6. Return max_len after loop finishes.

Complexity Analysis

  • Time: O(N)O(N) — We iterate through the string once with two pointers (left and right) that only move forward. Each character is processed a constant number of times (added to sum, removed from sum).
  • Space: O(1)O(1) auxiliary space if we compute costs on-the-fly or store them in an array (O(N)O(N)) — given the constraints, storing costs takes negligible memory compared to input storage. The logic uses only primitive variables for pointers and counters.

Solution

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        n = len(s)
        left = 0
        current_cost = 0
        max_len = 0
        
        # Precompute costs to avoid repeated ord() calls inside the loop logic 
        # though calculating on-the-fly is also O(N). Storing makes window shrink cleaner.
        cost_diffs = [abs(ord(s[i]) - ord(t[i])) for i in range(n)]

        right = 0
        while right < n:
            current_cost += cost_diffs[right]
            
            # If budget exceeded, shrink from the left until valid again
            while current_cost > maxCost:
                current_cost -= cost_diffs[left]
                left += 1
            
            # Update maximum length found so far
            if right - left + 1 > max_len:
                max_len = right - left + 1
                
            right += 1
        
        return max_len

Edge Cases Handled

  • Zero Budget (maxCost == 0): The while current_cost > maxCost loop ensures the window only includes indices where cost is exactly 0 (matching characters). If no matches exist, length remains 0.
  • No Valid Substring: If every single character change costs more than maxCost, the inner while loop will shrink the window to empty (left == right + 1) immediately after adding a new element that violates budget. The logic correctly returns 0 in this case (though constraints usually imply at least one match or maxCost allows some changes).
  • Large Inputs: Using two pointers ensures linear time complexity, preventing Time Limit Exceeded errors on N=105N=10^5.