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 ), integermaxCost. - Output: Integer representing max valid substring length.
- Constraints: Length up to , 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). maxCostcan be 0; this implies we can only keep substrings where for all indices in that substring.- Large input size () 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 to calculate the cost of transforming into . This involves iterating through all substrings () and summing costs for each (), resulting in or optimized to . Given the constraint of , this will time out.
However, notice that cost is always non-negative (absolute difference). This monotonicity suggests a Sliding Window approach:
- Expand the window by moving
rightforward and adding costs. - If the total cost exceeds
maxCost, shrink from the left (left) until valid again. - 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 time complexity.
Approach
- Initialize two pointers
left= 0 andright= 0, along with a running variablecurrent_cost. - Iterate through the string using
rightfrom 0 to . - Calculate cost for index
right:abs(ord(s[right]) - ord(t[right])). Add this tocurrent_cost. - While
current_cost > maxCost, subtract the cost of character atleftand incrementleft. This shrinks the window until it is valid again. - 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 ensuresright >= left). - Return
max_lenafter loop finishes.
Complexity Analysis
- Time: — We iterate through the string once with two pointers (
leftandright) that only move forward. Each character is processed a constant number of times (added to sum, removed from sum). - Space: auxiliary space if we compute costs on-the-fly or store them in an array () — 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): Thewhile current_cost > maxCostloop 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 .