1208. Get Equal Substrings Within Budget - Explanation

Description

The lowercase strings s and t have equal length. Changing s[i] to t[i] costs the absolute difference between their character codes; for example, changing a to d costs 3. Choose one contiguous interval and change its characters in s to match the characters at the same positions in t. Return the greatest interval length whose total cost is at most maxCost. Return 0 if no nonempty interval fits the budget.

Example 1:

Input: s = "abc"
t = "bcd"
maxCost = 2

Output: 2

Explanation: Each position costs 1 to change. Any two consecutive positions cost 2 and fit the budget, but all three cost 3. The maximum length is 2.

Example 2:

Input: s = "aaz"
t = "abz"
maxCost = 0

Output: 1

Explanation: The middle position costs 1, while the first and last positions already match. With a zero budget, either matching position can be chosen alone. They are not consecutive, so the maximum length is 1.

Example 3:

Input: s = "az"
t = "za"
maxCost = 24

Output: 0

Explanation: Each position costs 25 to change between a and z. The budget is only 24, so no nonempty interval is affordable and the answer is 0.

Constraints:

1 <= s.length <= 100000
t.length == s.length
s and t contain only lowercase English letters.
0 <= maxCost <= 1000000

Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Sliding Window - Maintaining a dynamic window over an array to find optimal subarrays
Two Pointers - Using left and right pointers to efficiently traverse and adjust window boundaries
ASCII Character Operations - Computing differences between character codes

1. Brute Force

Intuition

We want to find the longest substring where the total transformation cost stays within the budget. The transformation cost at each position is the absolute difference between the ASCII values of the corresponding characters. By checking every possible substring and tracking its cost, we can find the maximum valid length.

Algorithm

For each starting index i, try extending the substring to the right.
Maintain a running cost by adding |s[j] - t[j]| for each new character.
If the cost exceeds maxCost, stop extending from this start.
Track the maximum valid substring length found.
Return the maximum length.

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        n = len(s)
        res = 0

        for i in range(n):
            cur_cost = 0
            for j in range(i, n):
                cur_cost += abs(ord(t[j]) - ord(s[j]))
                if cur_cost > maxCost:
                    break
                res = max(res, j - i + 1)

        return res

public class Solution {
    public int equalSubstring(String s, String t, int maxCost) {
        int n = s.length();
        int res = 0;

        for (int i = 0; i < n; i++) {
            int curCost = 0;
            for (int j = i; j < n; j++) {
                curCost += Math.abs(t.charAt(j) - s.charAt(j));
                if (curCost > maxCost) {
                    break;
                }
                res = Math.max(res, j - i + 1);
            }
        }

        return res;
    }
}

class Solution {
public:
    int equalSubstring(string s, string t, int maxCost) {
        int n = s.size();
        int res = 0;

        for (int i = 0; i < n; i++) {
            int curCost = 0;
            for (int j = i; j < n; j++) {
                curCost += abs(t[j] - s[j]);
                if (curCost > maxCost) {
                    break;
                }
                res = max(res, j - i + 1);
            }
        }

        return res;
    }
};

class Solution {
    /**
     * @param {string} s
     * @param {string} t
     * @param {number} maxCost
     * @return {number}
     */
    equalSubstring(s, t, maxCost) {
        const n = s.length;
        let res = 0;

        for (let i = 0; i < n; i++) {
            let curCost = 0;
            for (let j = i; j < n; j++) {
                curCost += Math.abs(t.charCodeAt(j) - s.charCodeAt(j));
                if (curCost > maxCost) {
                    break;
                }
                res = Math.max(res, j - i + 1);
            }
        }

        return res;
    }
}

public class Solution {
    public int EqualSubstring(string s, string t, int maxCost) {
        int n = s.Length;
        int res = 0;

        for (int i = 0; i < n; i++) {
            int curCost = 0;
            for (int j = i; j < n; j++) {
                curCost += Math.Abs(t[j] - s[j]);
                if (curCost > maxCost) {
                    break;
                }
                res = Math.Max(res, j - i + 1);
            }
        }

        return res;
    }
}

func equalSubstring(s string, t string, maxCost int) int {
    n := len(s)
    res := 0

    for i := 0; i < n; i++ {
        curCost := 0
        for j := i; j < n; j++ {
            diff := int(t[j]) - int(s[j])
            if diff < 0 {
                diff = -diff
            }
            curCost += diff
            if curCost > maxCost {
                break
            }
            if j-i+1 > res {
                res = j - i + 1
            }
        }
    }

    return res
}

class Solution {
    fun equalSubstring(s: String, t: String, maxCost: Int): Int {
        val n = s.length
        var res = 0

        for (i in 0 until n) {
            var curCost = 0
            for (j in i until n) {
                curCost += kotlin.math.abs(t[j].code - s[j].code)
                if (curCost > maxCost) {
                    break
                }
                res = maxOf(res, j - i + 1)
            }
        }

        return res
    }
}

class Solution {
    func equalSubstring(_ s: String, _ t: String, _ maxCost: Int) -> Int {
        let sArr = Array(s)
        let tArr = Array(t)
        let n = sArr.count
        var res = 0

        for i in 0..<n {
            var curCost = 0
            for j in i..<n {
                curCost += abs(Int(tArr[j].asciiValue!) - Int(sArr[j].asciiValue!))
                if curCost > maxCost {
                    break
                }
                res = max(res, j - i + 1)
            }
        }

        return res
    }
}

impl Solution {
    pub fn equal_substring(s: String, t: String, max_cost: i32) -> i32 {
        let s = s.as_bytes();
        let t = t.as_bytes();
        let n = s.len();
        let mut res = 0;

        for i in 0..n {
            let mut cur_cost = 0;
            for j in i..n {
                cur_cost += (t[j] as i32 - s[j] as i32).abs();
                if cur_cost > max_cost {
                    break;
                }
                res = res.max(j - i + 1);
            }
        }

        res as i32
    }
}

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(1)$

2. Sliding Window

Intuition

Since we want the longest contiguous substring within a cost budget, a sliding window is ideal. We expand the window by moving the right pointer and shrink it from the left when the cost exceeds the budget. This efficiently explores all valid windows in linear time.

Algorithm

Initialize two pointers l and r at the start, and a running curCost of 0.
Expand the window by moving r and adding |s[r] - t[r]| to curCost.
While curCost exceeds maxCost, shrink the window by subtracting |s[l] - t[l]| and incrementing l.
Update the result with the current window size r - l + 1.
Return the maximum window size found.

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        curCost = 0
        l = 0
        res = 0

        for r in range(len(s)):
            curCost += abs(ord(s[r]) - ord(t[r]))
            while curCost > maxCost:
                curCost -= abs(ord(s[l]) - ord(t[l]))
                l += 1
            res = max(res, r - l + 1)

        return res

public class Solution {
    public int equalSubstring(String s, String t, int maxCost) {
        int curCost = 0, l = 0, res = 0;

        for (int r = 0; r < s.length(); r++) {
            curCost += Math.abs(s.charAt(r) - t.charAt(r));
            while (curCost > maxCost) {
                curCost -= Math.abs(s.charAt(l) - t.charAt(l));
                l++;
            }
            res = Math.max(res, r - l + 1);
        }

        return res;
    }
}

class Solution {
public:
    int equalSubstring(string s, string t, int maxCost) {
        int curCost = 0, l = 0, res = 0;

        for (int r = 0; r < s.length(); r++) {
            curCost += abs(s[r] - t[r]);
            while (curCost > maxCost) {
                curCost -= abs(s[l] - t[l]);
                l++;
            }
            res = max(res, r - l + 1);
        }

        return res;
    }
};

class Solution {
    /**
     * @param {string} s
     * @param {string} t
     * @param {number} maxCost
     * @return {number}
     */
    equalSubstring(s, t, maxCost) {
        let curCost = 0,
            l = 0,
            res = 0;

        for (let r = 0; r < s.length; r++) {
            curCost += Math.abs(s.charCodeAt(r) - t.charCodeAt(r));
            while (curCost > maxCost) {
                curCost -= Math.abs(s.charCodeAt(l) - t.charCodeAt(l));
                l++;
            }
            res = Math.max(res, r - l + 1);
        }

        return res;
    }
}

public class Solution {
    public int EqualSubstring(string s, string t, int maxCost) {
        int curCost = 0, l = 0, res = 0;

        for (int r = 0; r < s.Length; r++) {
            curCost += Math.Abs(s[r] - t[r]);
            while (curCost > maxCost) {
                curCost -= Math.Abs(s[l] - t[l]);
                l++;
            }
            res = Math.Max(res, r - l + 1);
        }

        return res;
    }
}

func equalSubstring(s string, t string, maxCost int) int {
    curCost, l, res := 0, 0, 0

    for r := 0; r < len(s); r++ {
        diff := int(s[r]) - int(t[r])
        if diff < 0 {
            diff = -diff
        }
        curCost += diff
        for curCost > maxCost {
            diff := int(s[l]) - int(t[l])
            if diff < 0 {
                diff = -diff
            }
            curCost -= diff
            l++
        }
        if r-l+1 > res {
            res = r - l + 1
        }
    }

    return res
}

class Solution {
    fun equalSubstring(s: String, t: String, maxCost: Int): Int {
        var curCost = 0
        var l = 0
        var res = 0

        for (r in s.indices) {
            curCost += kotlin.math.abs(s[r].code - t[r].code)
            while (curCost > maxCost) {
                curCost -= kotlin.math.abs(s[l].code - t[l].code)
                l++
            }
            res = maxOf(res, r - l + 1)
        }

        return res
    }
}

class Solution {
    func equalSubstring(_ s: String, _ t: String, _ maxCost: Int) -> Int {
        let sArr = Array(s)
        let tArr = Array(t)
        var curCost = 0
        var l = 0
        var res = 0

        for r in 0..<sArr.count {
            curCost += abs(Int(sArr[r].asciiValue!) - Int(tArr[r].asciiValue!))
            while curCost > maxCost {
                curCost -= abs(Int(sArr[l].asciiValue!) - Int(tArr[l].asciiValue!))
                l += 1
            }
            res = max(res, r - l + 1)
        }

        return res
    }
}

impl Solution {
    pub fn equal_substring(s: String, t: String, max_cost: i32) -> i32 {
        let s = s.as_bytes();
        let t = t.as_bytes();
        let mut cur_cost = 0;
        let mut l = 0;
        let mut res = 0;

        for r in 0..s.len() {
            cur_cost += (s[r] as i32 - t[r] as i32).abs();
            while cur_cost > max_cost {
                cur_cost -= (s[l] as i32 - t[l] as i32).abs();
                l += 1;
            }
            res = res.max(r - l + 1);
        }

        res as i32
    }
}

Time & Space Complexity

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

3. Sliding Window (Optimal)

Intuition

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.

Algorithm

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

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

public class Solution {
    public int equalSubstring(String s, String t, int maxCost) {
        int l = 0;
        for (int r = 0; r < s.length(); r++) {
            maxCost -= Math.abs(s.charAt(r) - t.charAt(r));
            if (maxCost < 0) {
                maxCost += Math.abs(s.charAt(l) - t.charAt(l));
                l++;
            }
        }
        return s.length() - 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;
    }
};

class Solution {
    /**
     * @param {string} s
     * @param {string} t
     * @param {number} maxCost
     * @return {number}
     */
    equalSubstring(s, t, maxCost) {
        let l = 0;
        for (let r = 0; r < s.length; r++) {
            maxCost -= Math.abs(s.charCodeAt(r) - t.charCodeAt(r));
            if (maxCost < 0) {
                maxCost += Math.abs(s.charCodeAt(l) - t.charCodeAt(l));
                l++;
            }
        }
        return s.length - l;
    }
}

public class Solution {
    public int EqualSubstring(string s, string t, int maxCost) {
        int l = 0;
        for (int r = 0; r < s.Length; r++) {
            maxCost -= Math.Abs(s[r] - t[r]);
            if (maxCost < 0) {
                maxCost += Math.Abs(s[l] - t[l]);
                l++;
            }
        }
        return s.Length - l;
    }
}

func equalSubstring(s string, t string, maxCost int) int {
    l := 0
    for r := 0; r < len(s); r++ {
        diff := int(s[r]) - int(t[r])
        if diff < 0 {
            diff = -diff
        }
        maxCost -= diff
        if maxCost < 0 {
            diff := int(s[l]) - int(t[l])
            if diff < 0 {
                diff = -diff
            }
            maxCost += diff
            l++
        }
    }
    return len(s) - l
}

class Solution {
    fun equalSubstring(s: String, t: String, maxCost: Int): Int {
        var cost = maxCost
        var l = 0
        for (r in s.indices) {
            cost -= kotlin.math.abs(s[r].code - t[r].code)
            if (cost < 0) {
                cost += kotlin.math.abs(s[l].code - t[l].code)
                l++
            }
        }
        return s.length - l
    }
}

class Solution {
    func equalSubstring(_ s: String, _ t: String, _ maxCost: Int) -> Int {
        let sArr = Array(s)
        let tArr = Array(t)
        var cost = maxCost
        var l = 0

        for r in 0..<sArr.count {
            cost -= abs(Int(sArr[r].asciiValue!) - Int(tArr[r].asciiValue!))
            if cost < 0 {
                cost += abs(Int(sArr[l].asciiValue!) - Int(tArr[l].asciiValue!))
                l += 1
            }
        }
        return sArr.count - l
    }
}

impl Solution {
    pub fn equal_substring(s: String, t: String, max_cost: i32) -> i32 {
        let s = s.as_bytes();
        let t = t.as_bytes();
        let mut cost = max_cost;
        let mut l = 0;

        for r in 0..s.len() {
            cost -= (s[r] as i32 - t[r] as i32).abs();
            if cost < 0 {
                cost += (s[l] as i32 - t[l] as i32).abs();
                l += 1;
            }
        }
        (s.len() - l) as i32
    }
}

Time & Space Complexity

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

Common Pitfalls

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.