LeetCode 2027. 转换字符串的最少操作次数
题目描述
给定仅包含 X 和 O 的字符串 s。每次选择字符串内三个连续位置，把这些位置全部变成 O，原本是 O 的位置保持不变。返回使整个字符串都变为 O 所需的最少操作次数。
示例 1：
输入：s = "XOXXOX"
输出：2
解释：处理下标 0…2 和 3…5 两个区间即可。
示例 2：
输入：s = "OOX"
输出：1
解释：选择整个字符串，将最后一个 X 变成 O。
示例 3：
输入：s = "OOOOO"
输出：0
解释：已经没有 X，无需操作。
提示：
- 3 ≤ s.length ≤ 1000。
- s 仅由 X 和 O 组成。
- 每次选择恰好三个连续位置，区间不能超出字符串范围。
题意分析
每次必须选择字符串内恰好三个连续位置，将它们全部置为
O，求消除所有X的最少操作次数。区间里原有的O可以一起处理，不会产生任何副作用。这是覆盖所有待处理
X的问题，不是翻转字符，也不要求每次选中的三个位置原本都是X。每次操作的实际区间必须在字符串内，题目保证长度至少为三。
解法：从最左未处理 X 开始覆盖
核心思路
[!blue]
从左向右扫描，保持当前位置之前的所有
X都已被此前操作覆盖。遇到O不需要付出操作，直接前进；遇到最左侧尚未覆盖的X，任何完整方案都必须至少有一次操作覆盖它。设这个位置为
i。覆盖它的长度三区间，起点不能在i的右侧。既然左边已经处理完成，就应让这次操作尽量向右伸展，使它顺便覆盖最多的后续位置，而不是把覆盖机会浪费在更左侧。这个选择不会增加最优次数：把某个覆盖
i的操作向右平移到最靠右的合法位置，失去的覆盖只位于已经处理好的左侧，i及原先覆盖的更右目标都不会漏掉。这样可以让一个最优方案包含当前贪心操作，再继续处理未覆盖后缀。通常区间是
[i, i + 2]，所以计数加一后可直接令i += 3。若i已靠近末尾，实际选择最后三个位置[n - 3, n - 1]，同样覆盖全部剩余字符。程序只求次数，无需真正修改字符串，跳到末尾之外表示剩余部分已经处理完，并不是执行越界操作。
解题步骤
- 从下标零开始，操作数初始化为零。
- 当前字符为
O时前进一步。- 当前字符为尚未覆盖的
X时，计一次操作，并将扫描位置前移三格。- 扫描结束返回次数；末尾不足三格时，实际操作区间向左贴齐字符串末端。
代码实现
class Solution {
public int minimumMoves(String s) {
int answer = 0;
for (int i = 0; i < s.length(); ) {
if (s.charAt(i) == 'X') {
answer++;
i += 3;
} else {
i++;
}
}
return answer;
}
}
func minimumMoves(s string) int {
answer := 0
for i := 0; i < len(s); {
if s[i] == 'X' {
answer++
i += 3
} else {
i++
}
}
return answer
}
复杂度分析
- 时间复杂度：$O(n)$，扫描下标只向右移动，不回头处理已覆盖字符。
- 空间复杂度：$O(1)$，只记录扫描位置与操作数，原字符串不修改。
关键点总结
[!green]
- 最左未覆盖的
X强制至少一次操作，尽量向右覆盖不损失已经处理的目标。- 一次操作可以覆盖多个
X，也可以包含原本已经正确的O。- 跳过三个位置表达已经覆盖的区间，无需逐字符改写。
- 末尾采用贴齐边界的合法区间，计数逻辑仍保持一致。
易错点总结
[!yellow]
- 每看到一个原始
X就加一次，忽略它可能已被前一次操作覆盖。- 只处理连续三个
X，遗漏区间中允许包含O的规则。- 把操作当成翻转，担心覆盖旧
O会变坏，错误限制了可选区间。- 最后不足三个位置就放弃，实际可以将区间左移到最后三个位置，仍只需一次。
- 将代码跳到数组末尾之外理解为实际区间也可以越界，混淆了计数扫描与操作位置。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 995. K 连续位的最小翻转次数 | 困难 | 同样从最左未处理位置决定覆盖操作，原题翻转会影响后续状态，本题直接置 O 且窗口长度固定为 3。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！