跳至主要內容

1208. 尽可能使字符串相等

ITCharge大约 2 分钟

1208. 尽可能使字符串相等open in new window

  • 标签:字符串、二分查找、前缀和、滑动窗口
  • 难度:中等

题目大意

给定两个长度相同的字符串,st。将 s 中的第 i 个字符变到 t 中的第 i 个字符需要 s[i]t[i]| s[i] - t[i] | 的开销(开销可能为 0),也就是两个字符的 ASCII 码值的差的绝对值。用于变更字符串的最大预算是 maxCost。在转化字符串时,总开销应当小于等于该预算,这也意味着字符串的转化可能是不完全的。

要求:如果你可以将 s 的子字符串转化为它在 t 中对应的子字符串,则返回可以转化的最大长度。如果 s 中没有子字符串可以转化成 t 中对应的子字符串,则返回 0

解题思路

维护一个滑动窗口 window_sum 用于记录窗口内的开销总和,保证窗口内的开销总和小于等于 maxCost。使用 ans 记录可以转化的最大长度。具体做法如下:

使用两个指针 leftright。分别指向滑动窗口的左右边界,保证窗口内所有元素转化开销总和小于等于 maxCost

  • 先统计出 s 中第 i 个字符变为 t 的第 i 个字符的开销,用数组 costs 保存。
  • 一开始,leftright 都指向 0
  • 将最右侧字符的转变开销填入窗口中,向右移动 right
  • 直到窗口内开销总和 window_sum 大于 maxCost。则不断右移 left,缩小窗口长度。直到 window_sum <= maxCost 时,更新可以转换的最大长度 ans
  • 向右移动 right,直到 right >= len(s) 为止。
  • 输出答案 ans

代码

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        size = len(s)
        costs = [0 for _ in range(size)]
        for i in range(size):
            costs[i] = abs(ord(s[i]) - ord(t[i]))

        left, right = 0, 0
        ans = 0
        window_sum = 0
        while right < size:
            window_sum += costs[right]
            while window_sum > maxCost:
                window_sum -= costs[left]
                left += 1
            ans = max(ans, right - left + 1)
            right += 1

        return ans