Get Equal Substrings Within Budget

Master this topic with zero to advance depth.

Get Equal Substrings Within Budget

Find the maximum length of a substring that can be transformed from s to t without exceeding maxCost.

Visual Representation

s = "abcd", t = "bcdf", maxCost = 3

Costs: |a-b|=1, |b-c|=1, |c-d|=1, |d-f|=2
Window [abc] -> [bcd]: Cost = 1+1+1 = 3 (<= 3) Len 3
Window [bcd] -> [cdf]: Cost = 1+1+2 = 4 (> 3) X

Medium

Examples

Input: s = "abcd", t = "bcdf", maxCost = 3
Output: 3

Approach 1

Level I: Brute Force

Intuition

Iterate through all possible substrings s[i...j]. For each substring, calculate the transformation cost by summing the absolute differences between s[k] and t[k] for all k in the range. If the cost $\le maxCost$ , track the length.

Thought Process

Outer loop i from 0 to n-1.
Inner loop j from i to n-1.
Calculate currentCost = sum(abs(s[k] - t[k])) for k from i to j.
If currentCost <= maxCost, maxLen = max(maxLen, j - i + 1).

⏱ O(N^2)💾 O(1)

Detailed Dry Run

j	Substrings	Cost	Max Len
0	'a'->'b'	1	1
1	'ab'->'bc'	1+1=2	2
2	'abc'->'bcd'	1+1+1=3	3
3	'abcd'->'bcdf'	3+2=5	3

java

public class Main {
    public static int equalSubstring(String s, String t, int maxCost) {
        int n = s.length(), maxLen = 0;
        for (int i = 0; i < n; i++) {
            int currentCost = 0;
            for (int j = i; j < n; j++) {
                currentCost += Math.abs(s.charAt(j) - t.charAt(j));
                if (currentCost <= maxCost) maxLen = Math.max(maxLen, j - i + 1);
                else break;
            }
        }
        return maxLen;
    }

    public static void main(String[] args) {
        System.out.println(equalSubstring("abcd", "bcdf", 3)); // 3
    }
}

Approach 2

Level II: Binary Search on Answer (O(N log N))

Intuition

We can binary search for the maximum possible length L of a valid substring. For a fixed length L, we use a sliding window of size L to check if at least one window satisfies the maxCost constraint.

Thought Process

Search range for L is [0, n].
In each step of binary search (length mid):
- Slide a window of size mid across the strings.
- Calculate the total cost of the window.
- If totalCost <= maxCost for any window, then mid is possible.
Adjust the search range accordingly.

Pattern: Search on Answer Space

⏱ O(N log N)💾 O(1)

java

public class Solution {
    public int equalSubstring(String s, String t, int maxCost) {
        int n = s.length(), low = 0, high = n, ans = 0;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (check(s, t, maxCost, mid)) {
                ans = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return ans;
    }

    private boolean check(String s, String t, int maxCost, int len) {
        int currentCost = 0;
        for (int i = 0; i < s.length(); i++) {
            currentCost += Math.abs(s.charAt(i) - t.charAt(i));
            if (i >= len) currentCost -= Math.abs(s.charAt(i - len) - t.charAt(i - len));
            
            if (i >= len - 1 && currentCost <= maxCost) return true;
        }
        return false;
    }
}

Approach 3

Level III: Optimal (Sliding Window)

Intuition

Thought Process

This is a standard variable-size sliding window problem on the array of transformation costs. We expand the window as long as the total cost is within the budget, and shrink from the left when it exceeds.

Patterns

Rolling Cost Sum: Add cost of element at Right.
Constraint Boundary: Move Left as long as Sum > Budget.
Max Length Utility: Result is max(Result, Right - Left + 1).

⏱ O(N)💾 O(1)

Detailed Dry Run

Right	Cost	Total Cost	Left	Max Len
0	1	1	0	1
1	1	2	0	2
2	1	3	0	3
3	2	5 -> 4	1	3

java

public class Main {
    public static int equalSubstring(String s, String t, int maxCost) {
        int n = s.length(), i = 0, j, res = 0, currentCost = 0;
        for (j = 0; j < n; j++) {
            currentCost += Math.abs(s.charAt(j) - t.charAt(j));
            while (currentCost > maxCost) {
                currentCost -= Math.abs(s.charAt(i) - t.charAt(i));
                i++;
            }
            res = Math.max(res, j - i + 1);
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(equalSubstring("abcd", "bcdf", 3));
    }
}

⚠️ Common Pitfalls & Tips

Be mindful of binary characters vs ASCII values. Use abs(ord(s[i]) - ord(t[i])) in Python or Math.abs(s.charCodeAt(i) - t.charCodeAt(i)) in JS.

← Previous QuestionReplace the Substring for Balanced String

Next Question →Subarrays with K Different Integers

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.