Sliding Window — Get Equal Substrings Within Budget

↗ LeetCode: Get Equal Substrings Within Budget · Medium · pattern chapter →

Given s, t, maxCost. Convert s[i] → t[i] costs |s[i] - t[i]|. Return longest substring convertible within budget.

Example 1 — s="abcd", t="bcdf", maxCost=3 → 3Example 2 — s="abcd", t="cdef", maxCost=3 → 1Example 3 — s="abcd", t="acde", maxCost=0 → 1

Constraints — 1 ≤ n ≤ 10⁵; 0 ≤ maxCost ≤ 10⁶.

Progressive Hints

Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.

---

⏱️Interview timer00:00

Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.

Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.

Approach — Sliding window on the diff array (canonical)

Insight. Compute diff[i] = |s[i] - t[i]|. Now: longest subarray with sum ≤ maxCost.

int equalSubstring(String s, String t, int maxCost) {
    int l = 0, cost = 0, best = 0;
    for (int r = 0; r < s.length(); r++) {
        cost += Math.abs(s.charAt(r) - t.charAt(r));
        while (cost > maxCost) cost -= Math.abs(s.charAt(l) - t.charAt(l++));
        best = Math.max(best, r - l + 1);
    }
    return best;
}

Execution Trace

Budget window — s='abcd', t='bcdf', maxCost=3

Step 1 / 21+1+1=3 ≤ 3 → best=3

Complexity — Time O(n); Space O(1).

---

Try it yourself

Complexity summary

Approach	Time	Space	Grade
Sliding budget	O(n)	O(1)	canonical

When to use which

• "Convert within budget" → diff array + sliding window.
• Multi-alphabet Unicode → codePoints instead of chars.
• "Return the substring" → track (bestL, bestLen) and slice.

✨AI Study CompanionBeta

Related problems

• Longest Substring with At Most K Distinct Characters
• Max Consecutive Ones III
• Minimum Size Subarray Sum

Was this page helpful?