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.

#1208

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

尽可能使字符串相等

给你两个长度相同的字符串， s 和 t 。将 s 中的第 i 个字符变到 t 中的第 i 个字符需要 |s[i] - t[i]| 的开销（开销可能为 0），也就是两个字符的 ASCII 码值的差的绝对值。用于变更字符串的最大预算是 maxCost 。在转化字符串时，总开销应当小于等于该预算，这也…

字符串二分查找滑动窗口前缀和

题目描述

给你两个长度相同的字符串，s 和 t。

将 s 中的第 i 个字符变到 t 中的第 i 个字符需要 |s[i] - t[i]| 的开销（开销可能为 0），也就是两个字符的 ASCII 码值的差的绝对值。

用于变更字符串的最大预算是 maxCost。在转化字符串时，总开销应当小于等于该预算，这也意味着字符串的转化可能是不完全的。

如果你可以将 s 的子字符串转化为它在 t 中对应的子字符串，则返回可以转化的最大长度。

如果 s 中没有子字符串可以转化成 t 中对应的子字符串，则返回 0。

示例 1：

输入：s = "abcd", t = "bcdf", maxCost = 3
输出：3
解释：s 中的 "abc" 可以变为 "bcd"。开销为 3，所以最大长度为 3。

示例 2：

输入：s = "abcd", t = "cdef", maxCost = 3
输出：1
解释：s 中的任一字符要想变成 t 中对应的字符，其开销都是 2。因此，最大长度为 1。

示例 3：

输入：s = "abcd", t = "acde", maxCost = 0
输出：1
解释：a -> a, cost = 0，字符串未发生变化，所以最大长度为 1。

提示：

1 <= s.length <= 10⁵
t.length == s.length
0 <= maxCost <= 10⁶
s 和 t 都只含小写英文字母。

lightbulb

解题思路

方法一：前缀和 + 二分查找

我们可以创建一个长度为 $n + 1$ 的数组 $f$ ，其中 $f[i]$ 表示字符串 $s$ 的前 $i$ 个字符与字符串 $t$ 的前 $i$ 个字符的 ASCII 码值的差的绝对值之和。这样，我们就可以通过 $f[j + 1] - f[i]$ 来计算字符串 $s$ 的第 $i$ 个字符到第 $j$ 个字符的 ASCII 码值的差的绝对值之和，其中 $0 \leq i \leq j < n$ 。

注意到长度具有单调性，即如果存在长度为 $x$ 的子串满足条件，那么长度为 $x - 1$ 的子串也一定满足条件。因此，我们可以使用二分查找的方法来求解最大长度。

我们定义函数 $check(x)$ ，表示是否存在长度为 $x$ 的子串满足条件。在该函数中，我们只需要枚举所有长度为 $x$ 的子串，判断其是否满足条件即可。如果存在满足条件的子串，那么函数返回 true，否则返回 false。

接下来，我们定义二分查找的左边界 $l$ 为 $0$ ，右边界 $r$ 为 $n$ 。在每一步中，我们令 $mid = \lfloor \frac{l + r + 1}{2} \rfloor$ ，如果函数 $check(mid)$ 的返回值为 true，那么我们将左边界更新为 $mid$ ，否则我们将右边界更新为 $mid - 1$ 。在二分查找结束后，我们得到的左边界即为答案。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为字符串 $s$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

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

speed

复杂度分析

指标	值
时间	O(N)
空间	O(1)

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#1004 最大连续1的个数 III #862 和至少为 K 的最短子数组 #1658 将 x 减到 0 的最小操作数