---

1540. K 次操作转变字符串

• 标签：哈希表、字符串
• 难度：中等

题目链接

• 1540. K 次操作转变字符串 - 力扣

题目大意

描述：给定两个字符串 $s$ 和 $t$，以及一个整数 $k$。每次操作可以选择一个下标 $i$（$0 \le i < s.length$）和一个 $1$ 到 $k$ 之间的整数 $shift$，将 $s[i]$ 循环右移 $shift$ 步（即 $s[i] = (s[i] - 'a' + shift) \% 26 + 'a'$）。

限制条件：

1. 每个 $i$ 只能被选择恰好一次。
2. 同一个 $shift$ 值只能被使用最多一次（即所有操作中使用的 $shift$ 值必须互不相同）。

要求：判断能否在 $k$ 次操作内将 $s$ 转换为 $t$。

说明：

• $1 \le s.length, t.length \le 10^5$。
• 如果 $s.length \neq t.length$，直接返回 False。
• $1 \le k \le 10^9$。

示例：

• 示例 1：

输入：s = "input", t = "ouput", k = 9
输出：true
解释：第 6 次操作时，我们将 'i' 切换 6 次得到 'o' 。第 7 次操作时，我们将 'n' 切换 7 次得到 'u' 。

• 示例 2：

输入：s = "abc", t = "bcd", k = 10
输出：false
解释：我们需要将每个字符切换 1 次才能得到 t 。我们可以在第 1 次操作时将 'a' 切换成 'b' ，但另外 2 个字母在剩余操作中无法再转变为 t 中对应字母。

解题思路

思路 1：贪心 + 计数

1. 核心思想

先检查长度是否相等。然后对于每个位置 $i$，计算 $s[i]$ 变成 $t[i]$ 所需的最小右移步数 $d$：

$$d = (t[i] - s[i] + 26) \% 26$$

如果 $d = 0$（字符已相同），该位置不需要操作。

对于 $d > 0$ 的位置，需要的 shift 值为 $d, d+26, d+52, \dots$（因为循环移 $d+26$ 与移 $d$ 的效果相同），且每个 shift 值只能用一次。

问题转化为：对于每个需要 $d$ 的位置，分配一个互不相同的 $shift$ 值（形式为 $d + 26 \times c$，$c \ge 0$），且所有 $shift \le k$。判断是否可行。

2. 具体步骤

第 1 步：若 $len(s) \neq len(t)$，返回 False。

第 2 步：用一个哈希表（或数组）count 统计每个 $d$ 值需要被使用的次数。对于每个 $i$，计算 $d = (t[i] - s[i] + 26) \% 26$，若 $d > 0$，$count[d] += 1$。

第 3 步：对于每个 $d \in [1, 25]$，需要的最大 shift 为：

$$needed = d + 26 \times (count[d] - 1)$$

因为同一个 $d$ 的第 $c$ 次出现需要 shift = $d + 26 \times c$（$c$ 从 $0$ 开始计数）。

第 4 步：如果所有 $d$ 的 $needed \le k$，返回 True，否则返回 False。

3. 正确性证明

• 每个位置 $i$ 需要的最小右移量 $d$ 是唯一确定的。
• 由于相同的 $d$ 值不能使用重复的 shift，第 $c$ 次出现的 $d$ 必须使用 $d + 26 \times c$（$c \ge 0$）。
• 最坏情况是 $d = 1$ 出现了很多次，需要的最大值为 $1 + 26 \times (count[1] - 1)$。
• 因此只需检查所有位置所需的最大 shift 值是否 $\le k$ 即可。

4. 举例说明

以 $s = "abc", t = "bcd", k = 3$ 为例：

• $i=0$：$s[0]='a' \to t[0]='b'$，$d = 1$，$count[1] = 1$，需要 shift = $1$。
• $i=1$：$s[1]='b' \to t[1]='c'$，$d = 1$，$count[1] = 2$，需要 shift = $1 + 26 = 27$。
• $i=2$：$s[2]='c' \to t[2]='d'$，$d = 1$，$count[1] = 3$，需要 shift = $1 + 52 = 53$。

只需 $k \ge 53$ 才能转换成功。这里 $k=3$，返回 False。

以 $s = "a", t = "a", k = 1$ 为例：

• $d = 0$，不需要操作。返回 True。

以 $s = "abc", t = "abcd", k = 3$ 为例：

• 长度不等，返回 False。

5. 注意事项

• $k$ 最大可达 $10^9$，因此比较时直接比较数值即可，不需要遍历到 $k$。
• $s$ 和 $t$ 的长度可达 $10^5$，计数数组长度为 $26$ 即可（$d \in [0, 25]$）。

思路 1：代码

class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t):
            return False

        count = [0] * 26
        for cs, ct in zip(s, t):
            d = (ord(ct) - ord(cs) + 26) % 26
            if d > 0:
                count[d] += 1

        for d in range(1, 26):
            if count[d] == 0:
                continue
            # 第 count[d] 次出现 d 需要的 shift
            needed = d + 26 * (count[d] - 1)
            if needed > k:
                return False

        return True

思路 1：复杂度分析

• 时间复杂度：$O(n + 26) = O(n)$，$n$ 为字符串长度。
• 空间复杂度：$O(26) = O(1)$，计数数组。