LeetCode 1208(尽可能使字符串相等)讲解

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)

代码实现

 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)。