尽可能使字符串相等

发表于
本文字数： 1.2k 阅读时长 ≈ 1 分钟

LeetCode每日一题，1208. Get Equal Substrings Within Budget

先看题目描述

y84vuV.png

大意就是给定两个字符串 s 和 t，将 s 中的字符 s[i] 替换成 t 中的字符 t[i] 需要的开销是两个字符的 ASCII 码值之差的绝对值，我们要保证替换字符的开销总和小于等于 maxCost，问 s 可以替换的子串最大长度是多少

算法和思路

滑动窗口

我们先进行预处理，用一个数组 cost 维护替换字符的开销，cost[i] 就表示将字符 s[i] 替换成 t[i] 需要的开销，我们用 cur 表示当前滑动窗口内替换字符的总开销，left 表示滑动窗口的左边界(闭区间)，right 表示滑动窗口的右边界(开区间)，每次通过判断 cur 是否大于 maxCost 来决定将滑动窗口移动还是扩张

  • 若 cur <= maxCost，说明此时滑动窗口的字符均可以替换，则将 right 右移，扩张当前滑动窗口
  • 若 cur > maxCost，则说明此时滑动窗口内的字符不可以全部替换，则将 left 和 right 加 1，将滑动窗口右移

最后返回滑动窗口的长度即可

算法源码

滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int equalSubstring(String s, String t, int maxCost) {
        int len = s.length();
        int[] cost = new int[len];
        char[] ss = s.toCharArray();
        char[] tt = t.toCharArray();
        for (int i = 0; i < len; i++) {
            cost[i] = Math.abs(ss[i] - tt[i]);
        }
        int left = 0;
        int right = 0;
        int cur = 0;
        while (right < len) {
            cur += cost[right];
            right++;
            if (cur > maxCost) {
                cur -= cost[left];
                left++;
            }
        }
        return right - left;
    }
}