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

Categories:

题目描述
思路分析
1. 解法一：滑动窗口（推荐）
相似题目

题目描述

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

思路分析

解法一：滑动窗口（推荐）

核心思路：

将每个位置的替换成本记为 abs(s[i] - t[i])。

维护窗口内成本和 cost，若超过 maxCost 则左指针右移。

记录窗口最大长度。

复杂度分析：

时间复杂度：O(n)，其中 n 表示字符串长度。

空间复杂度：O(1)。

class Solution {
    public int equalSubstring(String s, String t, int maxCost) {
        int left = 0;
        int cost = 0;
        int best = 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++;
            }

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

        return best;
    }
}

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

	for right := 0; right < len(s); right++ {
		if s[right] >= t[right] {
			cost += int(s[right] - t[right])
		} else {
			cost += int(t[right] - s[right])
		}

		for cost > maxCost {
			if s[left] >= t[left] {
				cost -= int(s[left] - t[left])
			} else {
				cost -= int(t[left] - s[left])
			}
			left++
		}

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

	return best
}

相似题目

题目	难度	考察点
1208. 尽可能使字符串相等	中等	滑动窗口
713. 乘积小于 K 的子数组	中等	滑动窗口
1004. 最大连续 1 的个数 III	中等	滑动窗口
159. 至多包含两个不同字符的最长子串	中等	滑动窗口
3. 无重复字符的最长子串	中等	滑动窗口

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/73571125