LeetCode 1208 - Get Equal Substrings Within Budget

Difficulty: 🟡 Medium
Topics: String, Binary Search, Sliding Window, Prefix Sum

Solution

Problem Understanding

The problem asks us to determine the longest contiguous substring of s that can be transformed into the corresponding substring of t without exceeding a given budget, maxCost. For each character in the substring, the transformation cost is the absolute difference between the ASCII values of the characters in s and t at the same position.

In other words, we want to maximize the length of a substring of s such that the sum of character transformation costs to match t does not exceed maxCost.

The inputs are two strings of equal length and an integer representing the maximum allowed cost. The output is a single integer, the maximum substring length under the cost constraint.

Key observations from the constraints are:

Strings can be up to 10^5 characters long, so any naive O(n²) solution will be too slow.
maxCost can be zero, which requires handling the case where no changes are allowed.
Both strings consist only of lowercase English letters, which simplifies ASCII computations.

Important edge cases include:

maxCost = 0 (cannot perform any character changes)
Strings where all characters are the same or all are different
Single-character strings (minimum length)

Approaches

Brute Force

The brute-force approach would iterate over all possible substrings of s, compute the cost of changing each substring to match t, and track the maximum length of those that are within maxCost. This works because it exhaustively considers every candidate substring.

However, this approach is too slow. For strings of length n, there are O(n²) possible substrings. Calculating the cost for each substring can take up to O(n) time, resulting in a total O(n³) time complexity, which is impractical for n = 10^5.

Optimal Approach

The optimal approach uses the sliding window technique. The key insight is that the problem asks for a contiguous substring, so we can maintain a window [left, right] over s. We expand the window by moving right forward and calculate the incremental cost of including the new character. If the total cost exceeds maxCost, we shrink the window from the left until the total cost is within the budget. This ensures we always maintain a valid window and can track the maximum window length efficiently.

This works because the cost function is additive and the characters’ transformations are independent, so expanding and contracting the window guarantees we do not miss any valid substring.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³)	O(1)	Check all substrings and compute cost
Sliding Window	O(n)	O(1)	Maintain running cost and adjust window dynamically

Algorithm Walkthrough

Initialize two pointers, left and right, both at 0. Also initialize totalCost to 0 and maxLen to 0.
Iterate right from 0 to n-1 (end of the string). For each character, calculate the cost of changing s[right] to t[right] and add it to totalCost.
If totalCost exceeds maxCost, move left forward and subtract the cost of s[left] -> t[left] from totalCost. Repeat until totalCost ≤ maxCost.
Update maxLen as the maximum of the current maxLen and the current window size right - left + 1.
Continue until right reaches the end of the string.
Return maxLen.

Why it works: The sliding window guarantees that for every ending index right, we find the longest valid substring ending there by dynamically adjusting left. Because cost is additive and the substring is contiguous, shrinking and expanding the window never misses a valid candidate.

Python Solution

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

Explanation: We iterate through s using right. For each character, we add the cost of transforming it to the corresponding t character. If the total cost exceeds maxCost, we move left forward to reduce the total cost until it fits within the budget. maxLen tracks the longest valid window.

Go Solution

func equalSubstring(s string, t string, maxCost int) int {
    left, totalCost, maxLen := 0, 0, 0
    
    for right := 0; right < len(s); right++ {
        totalCost += abs(int(s[right]) - int(t[right]))
        
        for totalCost > maxCost {
            totalCost -= abs(int(s[left]) - int(t[left]))
            left++
        }
        
        if right - left + 1 > maxLen {
            maxLen = right - left + 1
        }
    }
    
    return maxLen
}

func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}

Explanation: The Go version mirrors the Python solution. The main differences are explicit integer casting for ASCII values and defining a helper abs function. Slice indexing is used instead of a string iterator.

Worked Examples

Example 1: s = "abcd", t = "bcdf", maxCost = 3

right	char(s)	char(t)	cost	totalCost	left	maxLen
0	a	b	1	1	0	1
1	b	c	1	2	0	2
2	c	d	1	3	0	3
3	d	f	2	5	1	3

Result: 3

Example 2: s = "abcd", t = "cdef", maxCost = 3

right	char(s)	char(t)	cost	totalCost	left	maxLen
0	a	c	2	2	0	1
1	b	d	2	4	1	1
2	c	e	2	4	2	1
3	d	f	2	4	3	1

Result: 1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is visited at most twice, once by `right` and once by `left` pointer
Space	O(1)	Only a few integer variables are used, no extra arrays or data structures

The sliding window ensures linear time because left only moves forward and never backtracks, making the total number of pointer movements O(n).

Test Cases

# Provided examples
assert Solution().equalSubstring("abcd", "bcdf", 3) == 3  # Example 1
assert Solution().equalSubstring("abcd", "cdef", 3) == 1  # Example 2
assert Solution().equalSubstring("abcd", "acde", 0) == 1  # Example 3

# Edge cases
assert Solution().equalSubstring("a", "a", 0) == 1  # Single character, no cost needed
assert Solution().equalSubstring("a", "b", 0) == 0  # Single character, cost exceeds maxCost
assert Solution().equalSubstring("abcde", "zzzzz", 100) == 5  # Large budget allows full string
assert Solution().equalSubstring("abcde", "zzzzz", 1) == 0  # Very small budget, cannot change
assert Solution().equalSubstring("abcd", "abcd", 0) == 4  # Strings already equal

Test	Why
Single character, maxCost 0	Minimal input, no changes allowed
Single character, cost exceeds maxCost	Minimal input, change not allowed
Large budget	Entire string can be converted
Very small budget	Only substrings with zero cost allowed
Strings already equal	Budget irrelevant, should return full length

Edge Cases

maxCost = 0: This case tests if the algorithm correctly handles situations where no transformations are allowed. The implementation correctly uses the sliding window; if the first character's cost exceeds zero, the window shrinks to zero length, ensuring correctness.
Identical strings: If s and t are identical, the total transformation cost is zero for any substring. The algorithm handles this naturally because totalCost never increases, resulting in the window expanding to cover the full string.
Single-character strings: These cases test the lower bound. The