LeetCode 1208. 尽可能使字符串相等

约 4 分钟
文章信息 7 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 华为 商汤
标签
字符串 二分查找 滑动窗口 前缀和

题目描述

✅ 1208. 尽可能使字符串相等

image-20260928230356668

image-20260928230356670

题意分析

两个字符串长度相同，将 s[i] 改成 t[i] 的费用是字符码差的绝对值。要选择同一段连续下标，使这一段的总费用不超过 maxCost，并让长度最大。

各位置的费用可以独立相加，因此问题等价于：在一组非负费用中，寻找和不超过预算的最长连续区间。不能跳过中间昂贵的位置再拼接两端。

解法：滑动窗口维护预算

核心思路

[!blue]

用 [left, right] 表示当前窗口，cost 保存窗口内全部转换费用。每次向右加入一个位置，若费用超出预算，就依次减去左端费用并右移 left，直到窗口重新合法。

费用非负，所以向右扩展不会降低总费用，已经因超预算而舍弃的左端，之后也不可能重新合法；而移除左端不会增加费用。因此 left 只需向右走，不用回退。

收缩恰好在第一次满足预算时停止，得到的是当前右端对应的最早合法左端，也就是以该位置结尾的最长合法子串。遍历所有右端并记录最大长度，就覆盖了全局答案。费用可以直接由两个字符串计算，无需建立额外数组。

解题步骤

  1. 初始化 left = 0、cost = 0 和 ans = 0。
  2. right 每前进一步，把该位置的转换费用加入 cost。
  3. 只要 cost > maxCost，就减去当前左端费用，再执行 left++。一次删除可能仍不够，必须持续收缩。
  4. 费用恢复到预算内后，用 right - left + 1 更新答案。

单个位置也超预算时，窗口会收缩为空，left = right + 1，长度自然为零。预算为零时，费用为零的位置仍可以留在窗口内。

代码实现

class Solution {
    public int equalSubstring(String s, String t, int maxCost) {
        int left = 0;
        int cost = 0;
        int ans = 0;

        for (int right = 0; right < s.length(); right++) {
            cost += Math.abs(s.charAt(right) - t.charAt(right));

            // 收缩到预算内后，窗口才是当前右端的最长合法后缀。
            while (cost > maxCost) {
                // 减去即将离开窗口的位置费用，再推进左端。
                cost -= Math.abs(s.charAt(left) - t.charAt(left));
                left++;
            }

            ans = Math.max(ans, right - left + 1);
        }

        return ans;
    }
}

func equalSubstring(s string, t string, maxCost int) int {
    left := 0
    cost := 0
    ans := 0

    for right := 0; right < len(s); right++ {
        cost += absByteDiff(s[right], t[right])

        // 收缩到预算内后，窗口才是当前右端的最长合法后缀。
        for cost > maxCost {
            // 减去即将离开窗口的位置费用，再推进左端。
            cost -= absByteDiff(s[left], t[left])
            left++
        }

        if right-left+1 > ans {
            ans = right - left + 1
        }
    }

    return ans
}

func absByteDiff(a byte, b byte) int {
    if a >= b {
        return int(a - b)
    }
    return int(b - a)
}

复杂度分析

  • 时间复杂度：$O(n)$，左右下标各自最多前进 n 次。
  • 空间复杂度：$O(1)$。

关键点总结

[!green]

  • 预算允许恰好用满，只在大于时收缩。
  • 当前实现用 while 维持完整合法窗口，解释与更新时刻对应。

易错点总结

[!yellow]

  • 在收缩前记录长度，会把超预算区间计入。
  • 按费用排序会破坏子串必须连续的要求。
  • Go 直接对无符号字节做负差再转换，会得到错误费用，应先比较大小。

相似题目

题目 难度 关联与区别
1004. 最大连续1的个数 III 中等 同样把修改预算转成窗口成本，本题每个位置成本是字符码差，原题成本只为0或1。
209. 长度最小的子数组 中等 同样利用非负成本维持窗口单调性，原题求达到下界的最短段，本题求不超过上界的最长段。
424. 替换后的最长重复字符 中等 维护窗口内可消耗的修改预算；本题预算为对应字符差值之和，该题预算为窗口长度减最大字符频次。
2024. 考试的最大困扰度 中等 维护窗口内可消耗的修改预算；本题预算为对应字符差值之和，该题分别计算统一为两种答案时的窗口。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/73571125
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！