1208. 尽可能使字符串相等

🎯 问题描述（来源于LeetCode）

描述：
给你两个长度相同的字符串 s 和 t。
将 s 中的第 i 个字符变到 t 中的第 i 个字符需要 |s[i] - t[i]| 的开销（即两个字符 ASCII 码值的差的绝对值）。
用于变更字符串的最大预算是 maxCost。在转化字符串时，总开销应当小于等于该预算。
如果可以将 s 的某个子字符串转化为 t 中对应的子字符串，请返回可以转化的最大长度。
如果不存在可以转化的子字符串，返回 0。

说明：

  • 这是一个不定长滑动窗口问题。

  • 核心逻辑是维护一个窗口，使得窗口内所有字符的转换开销之和（总开销）不超过 maxCost。

  • 当总开销超过预算时，收缩左边界。

  • 示例：

  • 示例 1：

1
2
3
4
5
6
7
8
9
10
输入：s = "abcd", t = "bcdf", maxCost = 3
输出：3
解释：
s 中的 "abc" 可以转化为 t 中的 "bcd"。
开销分别为：|a-b|=1, |b-c|=1, |c-d|=1。
总开销 = 1+1+1 = 3 <= maxCost。
长度为 3。
````

- **示例 2**：

输入：s = “abcd”, t = “cdef”, maxCost = 3
输出：1
解释：
s 中的 “a” 转化为 “c” 开销为 2。
s 中的 “b” 转化为 “d” 开销为 2。
s 中的 “c” 转化为 “e” 开销为 2。
s 中的 “d” 转化为 “f” 开销为 2。
任意单个字符的开销都 <= 3，所以最大长度为 1。

1
2
3
4
5
## 💻 解题思路

### 思路1：不定长滑动窗口

#### 思路1：代码实现

class Solution:
def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
count = 0 # 记录满足条件的最长子字符串长度
fare = 0 # 记录当前窗口内的总开销
left = 0 # 窗口左边界

    # 右边界 right 随循环遍历字符串
    for right in range(len(s)):
        # 1. 扩展窗口：计算当前字符的转换开销并加入总开销
        f = abs(ord(s[right]) - ord(t[right]))
        fare += f
        
        # 2. 收缩窗口：如果总开销超过预算
        # 则不断移动左边界，直到总开销恢复为 <= maxCost
        while fare > maxCost:
            f = abs(ord(s[left]) - ord(t[left]))
            fare -= f
            left += 1
        
        # 3. 更新答案：此时窗口 [left, right] 内总开销 <= maxCost
        count = max(count, right - left + 1)
        
    return count


#### 思路1：📊 性能分析

- **时间复杂度**：O(N)
    - 其中N是字符串 `s` 的长度。
    - 虽然代码中有一个 `while` 循环嵌套在 `for` 循环中，但每个字符最多被访问两次（一次被右边界 `right` 加入，一次被左边界 `left` 移出）。因此，整体操作次数是线性的。
- **空间复杂度**：O(1)
    - 只使用了常数个额外变量 (`count`, `fare`, `left`, `right`, `f`)，没有使用额外的数据结构。

#### 思考

1. **不定长窗口**：
    
    - 右边界 `right` 始终向右移动。
    - 左边界 `left` 只有在总开销 `fare` 超过 `maxCost` 时才会向右移动。
2. **开销计算**：
    
    - 每个字符的转换开销是 `abs(ord(s[i]) - ord(t[i]))`。
    - 使用 `ord()` 函数获取字符的 ASCII 码值。
3. **收缩逻辑**：
    
    - `while fare > maxCost:` 是核心。它保证了在任何时刻，窗口内的总开销都不超过预算。
    - 当总开销超支时，我们不断移除左边的字符的开销，直到总开销恢复合法。
4. **答案更新时机**：
    
    - `count = max(count, right - left + 1)` 放在 `while` 循环之后。
    - 这保证了我们只在窗口满足“总开销 <= maxCost”这一合法条件时，才去更新最大长度。