leetcode 1208.尽可能使字符串相等 滑动窗口

题目描述

尽可能使字符串相等

---

思路

假定字符串 $s$ 和 $t$ 的长度均为 $n$，对于任意 $0\le i<n$，将 $s[i]$变成 $t[i]$ 的开销是 $|s[i]-t[i]|$
，因此可以创建一个长度为 $n$ 的数组$diff$，其中$diff[i]=|s[i]-t[i]|$。
创建数组 $diff$ 之后，问题转化成计算数组$diff$ 的元素和不超过 $maxCost$ 的最长子数组的长度。
由于 $diff$ 的的每个元素都是非负的，因此可以用滑动窗口的方法得到符合要求的最长子数组的长度。

滑动窗口的思想是，维护两个指针 $start$ 和 $end$ 表示数组 $diff$ 的子数组的开始下标和结束下标，满足子数组的元素和不超过 $maxCost$，子数组的长度是$end-start+1$。初始时，$start$ 和 $end$ 的值都是 $0$。
另外还要维护子数组的元素和 $sum$，初始值为 $0$。在移动两个指针的过程中，更新 $sum$ 的值，判断子数组的元素和是否大于 $maxCost$，并决定应该如何移动指针。

为了得到符合要求的最长子数组的长度，应遵循以下两点原则：

• 当 $start$ 的值固定时，$end$ 的值应尽可能大；
• 当 $end$ 的值固定时，$start$ 的值应尽可能小。

基于上述原则，滑动窗口的做法如下：

1. 将 $diff[end]$ 的值加到 $sum$；
2. 如果 $sum\le maxCost$，则子数组的元素和不超过 $maxCost$，使用当前子数组的长度 $end-start+1$ 更新最大子数组的长度；
3. 如果 $sum>maxCost$，则子数组的元素和大于 $maxCost$，需要向右移动指针 $start$ 并同时更新 $sum$的值，直到 $sum\le maxCost$，此时子数组的元素和不超过 $maxCost$，使用子数组的长度 $end-start+1$ 更新最大子数组的长度；
4. 将指针$end$ 右移一位，重复上述步骤，直到 $end$ 超出数组下标范围。

遍历结束之后，即可得到符合要求的最长子数组的长度，即字符串可以转化的最大长度。

---

代码

class Solution {
public:
    int equalSubstring(string s, string t, int maxCost) {
        int n=s.length();
        vector<int> diff(n,0);

        for(int i=0;i<n;i++)
            diff[i]=abs(s[i]-t[i]);

        int res=-1,sum=0;
        int start=0,end=0;
        while(end<n)
        {
            sum+=diff[end];
            while(sum>maxCost)
            {
                sum-=diff[start];
                start++;
            }
            res=max(res,end-start+1);
            end++;
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

---