#1208

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Get Equal Substrings Within Budget

Optimize substring transformations using a binary search approach to maximize the change within a budget.

string binary search sliding window prefix sum

Problem Statement

Given two strings, s and t, of the same length, and an integer maxCost, your task is to find the longest substring of s that can be transformed into the corresponding substring in t without exceeding the given cost. The cost of transforming the ith character of s to the ith character of t is defined as the absolute difference in their ASCII values.

The goal is to determine the maximum length of a substring that can be changed within the cost limit. If no such substring exists, return 0. The problem asks you to use an efficient approach that combines binary search and sliding window to calculate this maximum length.

Examples

Example 1

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

Output: 3

"abc" of s can change to "bcd". That costs 3, so the maximum length is 3.

Example 2

Input: s = "abcd", t = "cdef", maxCost = 3

Output: 1

Each character in s costs 2 to change to character in t, so the maximum length is 1.

Example 3

Input: s = "abcd", t = "acde", maxCost = 0

Output: 1

You cannot make any change, so the maximum length is 1.

Constraints

1 <= s.length <= 105
t.length == s.length
0 <= maxCost <= 106
s and t consist of only lowercase English letters.

Solution Approach

Binary Search over the Answer Space

Perform binary search on the possible maximum length of the substring. For each length, check if it’s possible to transform the substring within the given cost limit by using a sliding window.

Sliding Window for Cost Calculation

For each possible substring length, use a sliding window to efficiently compute the cost of transforming the substring. This ensures that we can handle large strings within the time limit.

Prefix Sum of Character Differences

Compute the cost of transformation by calculating the absolute differences between the corresponding characters of s and t. Use prefix sums to optimize this calculation, ensuring fast checks during the sliding window.

Complexity Analysis

Metric	Value
Time	O(N)
Space	O(1)

The time complexity is O(N) due to the binary search combined with a sliding window approach. Space complexity is O(1) since only a few variables are used for calculation.

What Interviewers Usually Probe

Ability to implement binary search over a valid range of answers.
Efficiency in using sliding window to avoid redundant recalculations.
Skill in optimizing cost calculations with prefix sums for large inputs.

Common Pitfalls or Variants

Common pitfalls

Not correctly managing the sliding window to ensure it stays within the maxCost limit.
Incorrectly applying binary search by not properly narrowing down the valid substring lengths.
Failure to efficiently calculate the cost of transformations, leading to unnecessary recomputation.

Follow-up variants

Allowing the cost to be greater than maxCost but still finding the longest possible substring within the budget.
Handling different types of cost calculations (e.g., other distance metrics).
Adapting the problem for non-ASCII character strings or other character sets.

FAQ

How can I solve the Get Equal Substrings Within Budget problem efficiently?

Use binary search over the possible answer space combined with a sliding window to calculate costs within the maxCost limit, ensuring efficient performance.

What is the optimal algorithm for Get Equal Substrings Within Budget?

The optimal solution involves binary search to narrow down the possible substring length and a sliding window to check if it fits within the cost limit.

How do I calculate the transformation cost between s and t?

The transformation cost is calculated as the absolute difference between the ASCII values of corresponding characters in s and t.

What if I can't find any valid substrings?

If no valid transformation is possible, return 0 as there is no substring that can be changed within the cost constraint.

What are the key performance considerations for this problem?

The key is to minimize recomputation using sliding window and prefix sums to handle the transformation cost efficiently, especially for larger inputs.

terminal

Solution

Solution 1: Prefix Sum + Binary Search

We can create an array $f$ of length $n + 1$, where $f[i]$ represents the sum of the absolute differences of ASCII values between the first $i$ characters of string $s$ and the first $i$ characters of string $t$. Thus, we can calculate the sum of the absolute differences of ASCII values from the $i$-th character to the $j$-th character of string $s$ by $f[j + 1] - f[i]$, where $0 \leq i \leq j < n$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        def check(x):
            for i in range(n):
                j = i + mid - 1
                if j < n and f[j + 1] - f[i] <= maxCost:
                    return True
            return False

        n = len(s)
        f = list(accumulate((abs(ord(a) - ord(b)) for a, b in zip(s, t)), initial=0))
        l, r = 0, n
        while l < r:
            mid = (l + r + 1) >> 1
            if check(mid):
                l = mid
            else:
                r = mid - 1
        return l

Solution 2: Two Pointers

We can maintain two pointers $l$ and $r$, initially $l = r = 0$; maintain a variable $\textit{cost}$, which represents the sum of the absolute values of the ASCII code differences in the index interval $[l,..r]$. In each step, we move $r$ to the right by one position, then update $\textit{cost} = \textit{cost} + |s[r] - t[r]|$. If $\textit{cost} \gt \textit{maxCost}$, then we loop to move $l$ to the right by one position, and decrease the value of $\textit{cost}$, until $\textit{cost} \leq \textit{maxCost}$. Then we update the answer, that is, $\textit{ans} = \max(\textit{ans}, r - l + 1)$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        def check(x):
            for i in range(n):
                j = i + mid - 1
                if j < n and f[j + 1] - f[i] <= maxCost:
                    return True
            return False

        n = len(s)
        f = list(accumulate((abs(ord(a) - ord(b)) for a, b in zip(s, t)), initial=0))
        l, r = 0, n
        while l < r:
            mid = (l + r + 1) >> 1
            if check(mid):
                l = mid
            else:
                r = mid - 1
        return l

Solution 3: Another Way of Using Two Pointers

In Solution 2, the interval maintained by the two pointers may become shorter or longer. Since the problem only requires the maximum length, we can maintain a monotonically increasing interval.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        def check(x):
            for i in range(n):
                j = i + mid - 1
                if j < n and f[j + 1] - f[i] <= maxCost:
                    return True
            return False

        n = len(s)
        f = list(accumulate((abs(ord(a) - ord(b)) for a, b in zip(s, t)), initial=0))
        l, r = 0, n
        while l < r:
            mid = (l + r + 1) >> 1
            if check(mid):
                l = mid
            else:
                r = mid - 1
        return l

Continue Practicing

#1004 max consecutive ones iii #862 shortest subarray with sum at least k #1658 minimum operations to reduce x to zero