Get Equal Substrings Within Budget

How it works

We can simplify the sliding window by never shrinking it more than one position at a time. Once we find a valid window of size k, we only care about finding windows of size k+1 or larger. If the current window is invalid, we slide both pointers together, maintaining the window size. The final answer is derived from the position of the left pointer l.

Steps

1. Start with l = 0 and iterate r from 0 to n-1.
2. Subtract |s[r] - t[r]| from maxCost.
3. If maxCost goes negative, add back |s[l] - t[l]| and increment l by one.
4. The window never shrinks below its maximum valid size.
5. Return n - l as the result.

Complexity

• Time complexity: O(n)
• Space complexity: O(1)

Things to watch for

Forgetting to Use Absolute Value for Cost Calculation

When computing the transformation cost between characters, you must use the absolute difference |s[i] - t[i]|. Forgetting to take the absolute value will produce negative costs when t[i] < s[i], leading to incorrect results. Always wrap the difference in abs() or Math.abs().

Shrinking the Window Too Aggressively

In the standard sliding window approach, when the cost exceeds the budget, you should shrink the window from the left one step at a time while updating the running cost. A common mistake is resetting the left pointer to right + 1 or incorrectly jumping the left pointer, which skips valid substrings and produces suboptimal answers.

Returning Window Size Instead of Maximum Length

The problem asks for the maximum length found across all valid windows, not the final window size. Make sure to track and update a separate result variable with max(result, r - l + 1) after each expansion, rather than just returning r - l + 1 at the end of the loop.

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        l = 0
        for r in range(len(s)):
            maxCost -= abs(ord(s[r]) - ord(t[r]))
            if maxCost < 0:
                maxCost += abs(ord(s[l]) - ord(t[l]))
                l += 1
        return len(s) - l

class Solution {
public:
    int equalSubstring(string s, string t, int maxCost) {
        int l = 0;
        for (int r = 0; r < s.length(); r++) {
            maxCost -= abs(s[r] - t[r]);
            if (maxCost < 0) {
                maxCost += abs(s[l] - t[l]);
                l++;
            }
        }
        return s.length() - l;
    }
};