1208. 尽可能使字符串相等
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)，只使用了常数空间来记录窗口的状态。