「滑动窗口」LeetCode 1208(尽可能使字符串相等)

警告
本文最后更新于 2023-02-15,文中内容可能已过时。

Leetcode 1208 题

抱歉拖更了,原本应该周一更新的拖到了周三。

题干简述

给定:两个字符串s和t,一个整型变量 maxCost。

要求:尽量将字符串s变成字符串t,且变换字符的总开销不高于 maxCost。

函数返回值:变换后的字符串s字符串t中的字符连续相同的最大长度。

开销计算公式:将 s 中的第 i 个字符变到 t 中的第 i 个字符需要|s[i] - t[i]| 的开销,也就是两个字符的 ASCII 码值的差的绝对值。

题目详情:https://leetcode.cn/problems/get-equal-substrings-within-budget/

解题思路

这是一个求解「最大子区间」问题,同时有 maxCost 做限制,所以适合使用「滑动窗口算法」:

  1. 构建两个变量:left、right,right-left的距离就是窗口的大小。
  2. 将开销记为 sumCost,同时right指针向右移动。
  3. 若 sumCost <= maxCost,left指针不动,窗口长度变大。
  4. 若 sumCost > maxCost,left指针向右移动,窗口长度不变。
  5. 最终right指针扫描整个数组,窗口的长度就是题解。

图解算法

(diffSum 就是上文的 sumCost)

img.png

img.png

img.png

img.png

img.png

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        sumCost = 0
        left = 0
        for right in range(0, len(s)):
            sumCost += abs(ord(s[right])-ord(t[right]))
            if sumCost > maxCost:
                sumCost -= abs(ord(s[left])-ord(t[left]))
                left += 1

        return len(s)-left

复杂度

时间复杂度O(N),空间复杂度O(1)。

img.png

Buy me a coffee~
室长 支付宝支付宝
室长 微信微信
0%