尽可能使字符串相等

标签: 字符串 二分查找 前缀和 滑动窗口

难度: Medium

给你两个长度相同的字符串，s 和 t。

将 s 中的第 i 个字符变到 t 中的第 i 个字符需要 |s[i] - t[i]| 的开销（开销可能为 0），也就是两个字符的 ASCII 码值的差的绝对值。

用于变更字符串的最大预算是 maxCost。在转化字符串时，总开销应当小于等于该预算，这也意味着字符串的转化可能是不完全的。

如果你可以将 s 的子字符串转化为它在 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
解释：a -> a, cost = 0，字符串未发生变化，所以最大长度为 1。

 

提示：

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

Submission

运行时间: 45 ms

内存: 0.0 MB

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        """
        requirements:
        total costs < = maxCost

        out: max length of substr

        """
        i = 0
        j = 0 
        max_len = 0
        length = 0
        total_costs = 0
        while i < len(s):
            cost = abs(ord(s[i]) - ord(t[i]))
            total_costs += cost

            if total_costs > maxCost:    
                length = i - j
                total_costs -= abs(ord(s[j])-ord(t[j]))
                j += 1
            else:
                length = i - j +1

            if length > max_len:
                max_len = length
            i += 1
        return max_len

Explain

此题解采用了滑动窗口的方法来解决问题。首先，定义两个指针i和j来表示当前考虑的子字符串s[j:i+1]的起始和结束位置。我们从字符串的开头开始遍历，对于每个字符位置i，计算将s[i]转换成t[i]的成本，并将其累加到total_costs中。若当前的总成本total_costs超过了maxCost，则需要调整窗口的左边界j，即缩小窗口，直到总成本小于等于maxCost。在此过程中，我们不断更新记录的最大长度max_len。这种方法能够高效地找到满足成本条件的最长子字符串。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        # 初始化两个指针和必要的变量
        i = 0
        j = 0 
        max_len = 0
        length = 0
        total_costs = 0
        # 遍历字符串s
        while i < len(s):
            # 计算当前位置字符转换的成本
            cost = abs(ord(s[i]) - ord(t[i]))
            total_costs += cost

            # 如果总成本超过预算，调整窗口左边界j
            if total_costs > maxCost:    
                length = i - j
                total_costs -= abs(ord(s[j])-ord(t[j]))
                j += 1
            else:
                # 更新当前窗口的长度
                length = i - j +1

            # 更新最大子字符串长度
            if length > max_len:
                max_len = length
            i += 1
        return max_len

Explore

滑动窗口算法在处理子数组或子字符串优化问题时非常高效，尤其是在需要连续子段的场景中。对于本题，目标是找到成本不超过maxCost的最长子字符串，滑动窗口算法可以在O(n)时间内解决，因为它可以不断调整窗口的大小而无需重新计算已考虑的字符。相对于动态规划，滑动窗口算法在空间复杂度上更优，通常只需要O(1)额外空间。动态规划虽然能够解决，但其通常需要O(n)的空间，并且对于每个状态的转移不如滑动窗口直观且高效。

在滑动窗口算法中，当总成本刚好等于maxCost时，这意味着当前窗口仍符合条件，因此可以继续向右扩展窗口，尝试包含下一个元素。这是因为下一个元素可能无需任何成本即可转换（即s[i+1]等于t[i+1]），或者在接下来的迭代中可以通过调整左边界j来平衡成本。只有当总成本确实超过maxCost时，我们才需要调整j以缩小窗口。

在滑动窗口算法中，每个字符被移除的情况发生在左指针j向右移动时。一旦j越过某个字符位置，这个字符就从当前考虑的窗口中移除了。由于j只会从左到右单向移动，每个字符位置一旦被j越过，就不会再被重新考虑进窗口，因此每个字符最多被移除一次。这一点确保了算法的效率和简洁性。

在当前题目的上下文中，将left指针（即j）向右移动一位是为了逐渐减少窗口的总成本，从而使其再次符合不超过maxCost的条件。这种方法简单且有效，因为每次只调整一位可以精确地控制总成本的减少，避免过度调整。尽管可以考虑其他策略如跳跃式移动j指针，但这可能导致不必要的复杂度增加或在减少成本时失去精准控制。当前的实现保证了算法的高效性和易于理解。