09-Get-Equal-Substrings-Within-Budget.md

Get Equal Substrings Within Budget

Problem Link

https://leetcode.com/problems/get-equal-substrings-within-budget/

---

Pattern

• Sliding Window

---

Approach

Sliding window tracking cost to convert substring; expand right and shrink left if cost exceeds budget.

---

Time Complexity

O(n)

Space Complexity

O(1)

---

Java Solution

class Solution {
    public int equalSubstring(String s, String t, int maxCost) {
        int left = 0, cost = 0, ans = 0;
        for (int right = 0; right < s.length(); right++) {
            cost += Math.abs(s.charAt(right) - t.charAt(right));
            while (cost > maxCost) {
                cost -= Math.abs(s.charAt(left) - t.charAt(left));
                left++;
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}