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
PreviewRecognizing 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…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewUse two pointers, left and right, to define a sliding window over the strings. Incrementally add the cost of the character difference at right…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
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
To iterate over the string with the right pointer, adding character difference costs and adjusting the left pointer to maintain the maxCost constraint.
Update Maximum Valid Substring Length
To record the longest substring length found so far that satisfies the cost constraint.
Return the Maximum Length Found
To output the final result after processing the entire string.
3 more steps with full analysis available on Pro.
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.
Full line-by-line criticality + rationale for all 10 lines available on Pro.
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?
See the answer with Pro.
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