Medium

题目描述

给你两个长度相同的字符串 s 和 t，以及一个整数 maxCost。

你希望将 s 变成 t。将 s 的第 i 个字符变成 t 的第 i 个字符需要花费 |s[i] - t[i]|（即两个字符的 ASCII 值差的绝对值）。

返回在花费不超过 maxCost 的前提下，能够变成与 t 对应子串相同的 s 子串的最大长度。如果没有子串可以在预算内变成对应的 t 子串，则返回 0。

示例 1：

输入：s = "abcd", t = "bcdf", maxCost = 3
输出：3
解释：s 中的 "abc" 可以变成 "bcd"，花费为 3，所以最大长度为 3。

示例 2：

输入：s = "abcd", t = "cdef", maxCost = 3
输出：1
解释：s 中的每个字符变成 t 中对应字符的花费都是 2，所以最大长度是 1。

示例 3：

输入：s = "abcd", t = "acde", maxCost = 0
输出：1
解释：无法进行任何改变，所以最大长度是 1。

约束条件：

  • 1 <= s.length <= 10^5
  • t.length == s.length
  • 0 <= maxCost <= 10^6
  • s 和 t 只包含小写英文字母

解题思路

这道题是一个经典的滑动窗口问题。我们需要找到最长的连续子串，使得将其变成对应的 t 子串的成本不超过 maxCost。

核心思路：

  1. 首先计算每个位置上的变换成本 cost[i] = |s[i] - t[i]|
  2. 使用滑动窗口技术，维护一个窗口 [left, right]，使得窗口内所有位置的成本总和不超过 maxCost
  3. 当窗口内成本总和超过限制时，移动左边界缩小窗口
  4. 在整个过程中记录满足条件的最大窗口长度

算法步骤：

  • 使用两个指针 left 和 right 表示窗口边界
  • right 指针向右扩展窗口，同时累加当前位置的成本
  • 当总成本超过 maxCost 时，移动 left 指针直到成本满足条件
  • 更新最大长度为 right - left + 1

这种方法的优势在于每个元素最多被访问两次（一次被 right 指针，一次被 left 指针），时间复杂度为 O(n)。

代码实现

class Solution {
public:
    int equalSubstring(string s, string t, int maxCost) {
        int n = s.length();
        int left = 0, currentCost = 0, maxLen = 0;
        
        for (int right = 0; right < n; right++) {
            currentCost += abs(s[right] - t[right]);
            
            while (currentCost > maxCost) {
                currentCost -= abs(s[left] - t[left]);
                left++;
            }
            
            maxLen = max(maxLen, right - left + 1);
        }
        
        return maxLen;
    }
};

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        n = len(s)
        left = 0
        current_cost = 0
        max_len = 0
        
        for right in range(n):
            current_cost += abs(ord(s[right]) - ord(t[right]))
            
            while current_cost > maxCost:
                current_cost -= abs(ord(s[left]) - ord(t[left]))
                left += 1
            
            max_len = max(max_len, right - left + 1)
        
        return max_len

public class Solution {
    public int EqualSubstring(string s, string t, int maxCost) {
        int n = s.Length;
        int left = 0, currentCost = 0, maxLen = 0;
        
        for (int right = 0; right < n; right++) {
            currentCost += Math.Abs(s[right] - t[right]);
            
            while (currentCost > maxCost) {
                currentCost -= Math.Abs(s[left] - t[left]);
                left++;
            }
            
            maxLen = Math.Max(maxLen, right - left + 1);
        }
        
        return maxLen;
    }
}

var equalSubstring = function(s, t, maxCost) {
    const n = s.length;
    let left = 0, currentCost = 0, maxLen = 0;
    
    for (let right = 0; right < n; right++) {
        currentCost += Math.abs(s.charCodeAt(right) - t.charCodeAt(right));
        
        while (currentCost > maxCost) {
            currentCost -= Math.abs(s.charCodeAt(left) - t.charCodeAt(left));
            left++;
        }
        
        maxLen = Math.max(maxLen, right - left + 1);
    }
    
    return maxLen;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)每个元素最多被访问两次，n 为字符串长度
空间复杂度O(1)只使用了常数个变量

相关题目