Get Equal Substrings Within Budget
Problem
Given two strings s and t of the same length and an integer maxCost, return the maximum length of a substring of s that can be changed to the corresponding substring of t with a total cost less than or equal to maxCost, where the cost of changing a character is the absolute difference of their ASCII values.
- 1 ≤ s.length, t.length ≤ 10⁵
- s.length == t.length
- 0 ≤ maxCost ≤ 10⁶
- s and t consist of lowercase English letters only
Example
s = "abcd", t = "bcdf", maxCost = 33Calculate the cost array as [1,1,1,2] representing the absolute differences between corresponding characters. Using a sliding window, the substring from index 0 to 2 ('abc' to 'bcd') has a total cost of 3, which is within maxCost. Extending to index 3 would exceed maxCost. Thus, the maximum length is 3.
Approach
Straightforward Solution
A brute-force approach would check every substring, calculate its cost, and track the maximum length under maxCost. This approach is O(n^2) and infeasible for large inputs.
Core Observation
The problem reduces to finding the longest contiguous subarray where the sum of absolute differences between s and t characters is at most maxCost. This is a classic sliding window problem where the window expands while the cost is affordable and contracts when it exceeds maxCost.
Path to Optimal
Recognizing the problem as a longest subarray with sum constraint allows the use of a sliding window. By maintaining two pointers and a running cost sum, the window expands by moving the right pointer and contracts by moving the left pointer when the cost exceeds maxCost. This approach achieves O(n) time complexity.
Optimal Approach
Use two pointers, left and right, to define a sliding window over the strings. Incrementally add the cost of the character difference at right. If the total cost exceeds maxCost, move left forward, subtracting the cost of the character difference at left. Track the maximum window size where the cost is within maxCost. This guarantees a single pass with O(n) time and O(1) extra space.
Time
O(n)
Each character is visited at most twice: once when the right pointer expands the window and once when the left pointer contracts it, resulting in linear time.
Space
O(1)
Only a few integer variables are used to track pointers and running cost; no additional data structures proportional to input size are needed.
Pattern Spotlight
Sliding Window (Variable Size Window with Sum Constraint)
When asked for the longest or shortest contiguous subarray satisfying a sum or cost constraint, use a sliding window that expands until the constraint is violated, then contracts from the left to restore feasibility, maintaining a running sum to achieve O(n) time.
Solution
| 1 | class Solution: |
| 2 | def equalSubstring(self, s: str, t: str, maxCost: int) -> int: |
| 3 | left = 0 |
| 4 | cost = 0 |
| 5 | best = 0 |
| 6 | |
| 7 | for right in range(len(s)): |
| 8 | cost += abs(ord(s[right]) - ord(t[right])) |
| 9 | |
| 10 | while cost > maxCost: |
| 11 | cost -= abs(ord(s[left]) - ord(t[left])) |
| 12 | left += 1 |
| 13 | |
| 14 | best = max(best, right - left + 1) |
| 15 | |
| 16 | return best |
Step-by-Step Solution
Initialize Sliding Window Pointers and Cost Accumulator
| 3 | left = 0 |
| 4 | cost = 0 |
| 5 | best = 0 |
Objective
To set up the initial state for the sliding window traversal, including the left pointer, running cost, and best maximum length found.
Key Insight
Starting with left at 0 and cost at 0 establishes the initial empty window. The best variable tracks the longest valid substring length found so far. This setup is essential to begin the incremental expansion and contraction of the window.
Interview Quick-Check
Core Logic
Initializing pointers and accumulators before the loop is critical to correctly track the window boundaries and cost.
State & Boundaries
left pointer starts at 0, representing the start of the window; cost starts at 0 since no characters are included yet.
Expand Window and Accumulate Cost While Maintaining Constraint
| 7 | for right in range(len(s)): |
| 8 | cost += abs(ord(s[right]) - ord(t[right])) |
| 10 | while cost > maxCost: |
| 11 | cost -= abs(ord(s[left]) - ord(t[left])) |
| 12 | left += 1 |
Objective
To iterate over the string with the right pointer, adding character difference costs and adjusting the left pointer to maintain the maxCost constraint.
Key Insight
By adding the absolute difference of characters at the right pointer, the window cost increases. If the cost exceeds maxCost, the window is shrunk from the left by subtracting the left character's cost and moving left forward. This dynamic adjustment ensures the window always represents the longest valid substring ending at right.
Interview Quick-Check
Core Logic
The sliding window expands by moving right and accumulates cost, then contracts by moving left when cost exceeds maxCost, maintaining a valid window.
State & Boundaries
The while loop condition ensures the window is shrunk until the cost is within maxCost, preserving correctness.
Common Pitfalls & Bugs
Forgetting to subtract the left character's cost when moving left pointer leads to incorrect cost tracking and invalid windows.
Complexity
Each character is processed at most twice, ensuring O(n) time complexity.
Update Maximum Valid Substring Length
| 14 | best = max(best, right - left + 1) |
Objective
To record the longest substring length found so far that satisfies the cost constraint.
Key Insight
After adjusting the window to be valid, the length of the current window (right - left + 1) is a candidate for the maximum length. Updating best with the maximum ensures the algorithm returns the longest valid substring length after processing all characters.
Interview Quick-Check
Core Logic
Updating the maximum length after each valid window expansion ensures the final answer reflects the longest feasible substring.
State & Boundaries
The window length calculation accounts for zero-based indexing by adding 1.
Return the Maximum Length Found
| 16 | return best |
Objective
To output the final result after processing the entire string.
Key Insight
Returning best after the loop completes provides the maximum length of any substring meeting the cost constraint. This final step concludes the algorithm.
Interview Quick-Check
Core Logic
Returning the tracked maximum length is the culmination of the sliding window process.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
cost += abs(ord(s[right]) - ord(t[right]))Add the absolute difference of the characters at the right pointer to the running cost.
Incrementally updating the cost with the difference at the new right boundary allows efficient tracking of the total cost of the current window without recomputing from scratch.
while cost > maxCost:While the running cost exceeds maxCost, shrink the window from the left.
This loop ensures the window remains valid by removing characters from the left until the total cost is within the allowed budget, maintaining correctness.
cost -= abs(ord(s[left]) - ord(t[left]))Subtract the absolute difference of the characters at the left pointer from the running cost.
Removing the leftmost character's cost from the total cost correctly updates the window's cost as it shrinks, preventing overcounting.
best = max(best, right - left + 1)Update the best maximum substring length with the current window size if larger.
Recording the maximum window size found so far ensures the algorithm returns the longest valid substring length after processing all characters.
cost = 0Initialize the running cost accumulator to 0.
The cost variable tracks the total cost of changing characters in the current window; starting at 0 reflects an empty window with no cost.
left += 1Move the left pointer forward to shrink the window.
Advancing the left pointer reduces the window size, enabling the algorithm to restore feasibility when the cost exceeds maxCost.
return bestReturn the maximum substring length found after processing the entire string.
This final return statement outputs the correct answer, concluding the algorithm.
left = 0Initialize the left pointer of the sliding window to 0.
Starting the left pointer at 0 sets the initial window boundary, enabling the window to expand from the start of the string.
best = 0Initialize the variable to track the best (maximum) substring length found.
Tracking the best length is essential to record the longest valid substring as the window moves through the string.
for right in range(len(s)):Iterate over the string with the right pointer to expand the sliding window.
The right pointer moves forward to include new characters, enabling exploration of all possible substrings in a single pass.
Test Your Understanding
Why does moving the left pointer forward when the cost exceeds maxCost guarantee that the window remains valid and that the maximum length is found?
Because the cost sum is strictly reduced by removing the leftmost character's cost, restoring feasibility. This process ensures all valid windows are considered, and the maximum length is updated only when the window is valid, guaranteeing correctness.
Related Problems
Sliding Window pattern
Don't just read it. Drill it.
Reconstruct Get Equal Substrings Within Budget from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Get Equal Substrings Within Budget drill