Problem: 1208. 尽可能使字符串相等

题目描述

给定两个相同长度的字符串 s 和 t，将字符串 s 转换为字符串 t 需要消耗开销，开销是两个字符的 ASCII 码差值的绝对值。还有一个最大预算 maxCost，我们需要在这个预算范围内，找到 s 中能够转换为 t 的最长子字符串，返回这个子字符串的长度。

示例

示例 1:

输入：s = "abcd", t = "bcdf", maxCost = 3
输出：3
解释：将 "abc" 变为 "bcd" 的总开销为 3，所以最长可转换子字符串长度为 3。

示例 2:

输入：s = "abcd", t = "cdef", maxCost = 3
输出：1
解释：每个字符的转换开销都为 2，因此只能转换单个字符。

代码实现

class Solution {
public:
    int equalSubstring(string s, string t, int maxCost) {
        int n = s.length(), ans = 0, left = 0;
        int window = 0;

        for (int right = 0; right < n; right++) {
            int c = abs(s[right] - t[right]);  // 计算当前字符转换开销
            window += c;  // 累计窗口内的总开销

            // 当总开销超过 maxCost 时，移动左指针缩小窗口
            while (window > maxCost) {
                window -= abs(s[left] - t[left]);  // 移除左边的开销
                left++;
            }

            // 更新最大可转换子字符串的长度
            ans = max(ans, right - left + 1);
        }

        return ans;
    }
};

题解

1. 解题思路

这道题可以用滑动窗口来解决。滑动窗口是一种常见的算法思想，它通过动态调整窗口的大小来解决问题。具体步骤如下：

• 使用两个指针 left 和 right 来表示窗口的左右边界，left 是窗口的起点，right 是窗口的终点。
• 在遍历字符串的过程中，不断累加从 s 转换到 t 的字符开销。
• 如果当前窗口内的总开销超过了 maxCost，则移动 left 指针缩小窗口，直到总开销重新符合条件。
• 在每次符合条件时，计算并更新当前可转换的最大子字符串长度。

2. 变量解释

• n: 字符串 s 和 t 的长度，假设两者长度相同。
• left: 滑动窗口的左边界，用来控制窗口缩小。
• right: 滑动窗口的右边界，用来控制窗口扩大。
• window: 记录当前窗口内的转换开销总和。
• c: 当前窗口中 s[right] 转换为 t[right] 的开销，即 abs(s[right] - t[right])。
• ans: 最终的答案，表示最长的可转换子字符串长度。

3. 滑动窗口详解

滑动窗口的核心在于：

• 当总开销 window 小于等于 maxCost 时，我们可以扩大窗口的右边界 right，并更新当前窗口的长度。
• 当总开销 window 超过 maxCost 时，需要移动左边界 left，缩小窗口，直到开销重新回到预算范围内。

通过这种方式，我们可以在 O(n) 的时间复杂度下完成遍历，并且只使用了常量空间 O(1)，因此该解法非常高效。

4. 代码逻辑解析

• 首先初始化 left 和 right 指针，window 用于记录当前窗口的总开销。
• 在 for 循环中，遍历字符串的每一个字符，计算转换的开销，并更新 window。
• 如果 window 超过了 maxCost，通过 while 循环移动 left 指针，缩小窗口，并减少开销。
• 每次窗口有效时，更新最大可转换子字符串的长度。

时间复杂度和空间复杂度

• 时间复杂度：O(n)，其中 n 是字符串的长度。每个字符最多被访问两次（一次进入窗口，一次离开窗口）。
• 空间复杂度：O(1)，只使用了常数空间来记录窗口的状态。