Get Equal Substrings Within Budget
Explanation & Solution
Description
You are given two strings s and t of the same length and an integer maxCost.
You want to change s to t. Changing the ith character of s to the ith character of t costs |s[i] - t[i]| (the absolute difference of the ASCII values).
Return the maximum length of a substring of s that can be changed to be the same as the corresponding substring of t with a total cost less than or equal to maxCost. If there is no substring that can be changed, return 0.
Examples
Input: s = "abcd", t = "bcdf", maxCost = 3
Output: 3
Explanation: Costs per character: |a-b|=1, |b-c|=1, |c-d|=1, |d-f|=2. The substring "abc" → "bcd" costs 1+1+1=3 ≤ 3, giving length 3.
Input: s = "abcd", t = "cdef", maxCost = 3
Output: 1
Explanation: Costs: 2, 2, 2, 2. Each character costs 2, so at most one character can be changed within budget 3.
Input: s = "abcd", t = "acde", maxCost = 0
Output: 1
Explanation: Costs: 0, 1, 1, 1. Index 0 has cost 0, so a substring of length 1 at index 0 is free.
Constraints
1 <= s.length <= 10^5t.length == s.length0 <= maxCost <= 10^6sandtconsist of lowercase English letters only.
Approach
Sliding Window pattern
1. Compute the Cost Array Implicitly
For each index i, the cost of changing s[i] to t[i] is |s.charCodeAt(i) - t.charCodeAt(i)|. Rather than precomputing an array, we calculate this on the fly as the window expands and contracts.
2. Initialize the Sliding Window
Set a left pointer at 0, a running currentCost at 0, and maxLen at 0 to track the longest valid window seen.
3. Expand the Window
Iterate with a right pointer across the string. At each step, add the cost of the current character to currentCost.
4. Shrink When Over Budget
If currentCost exceeds maxCost, subtract the cost of the character at left from currentCost and increment left. Repeat until the window cost is within budget.
5. Track the Maximum Length
After adjusting the window, compute the current window size (right - left + 1). Update maxLen if this is the largest valid window so far.
6. Return the Result
After processing all characters, return maxLen as the answer.
Key Insight
This is a classic variable-size sliding window on a derived cost array. Since costs are non-negative, expanding the window can only increase the total cost, and shrinking can only decrease it. This monotonic property guarantees the sliding window correctly finds the longest subarray with sum ≤ maxCost in O(n) time.
Visualization
Press ▶ or use ← → to step through