1208. 尽可能使字符串相等
大约 2 分钟
1208. 尽可能使字符串相等
- 标签:字符串、二分查找、前缀和、滑动窗口
- 难度:中等
题目大意
给定两个长度相同的字符串,s
和 t
。将 s
中的第 i
个字符变到 t
中的第 i
个字符需要 的开销(开销可能为 0
),也就是两个字符的 ASCII 码值的差的绝对值。用于变更字符串的最大预算是 maxCost
。在转化字符串时,总开销应当小于等于该预算,这也意味着字符串的转化可能是不完全的。
要求:如果你可以将 s
的子字符串转化为它在 t
中对应的子字符串,则返回可以转化的最大长度。如果 s
中没有子字符串可以转化成 t
中对应的子字符串,则返回 0
。
解题思路
维护一个滑动窗口 window_sum
用于记录窗口内的开销总和,保证窗口内的开销总和小于等于 maxCost
。使用 ans
记录可以转化的最大长度。具体做法如下:
使用两个指针 left
、right
。分别指向滑动窗口的左右边界,保证窗口内所有元素转化开销总和小于等于 maxCost
。
- 先统计出
s
中第i
个字符变为t
的第i
个字符的开销,用数组costs
保存。 - 一开始,
left
、right
都指向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