LeetCode 题解工作台
转换字符串的最少操作次数
给你一个字符串 s ，由 n 个字符组成，每个字符不是 'X' 就是 'O' 。 一次 操作 定义为从 s 中选出 三个连续字符 并将选中的每个字符都转换为 'O' 。注意，如果字符已经是 'O' ，只需要保持 不变 。 返回将 s 中所有字符均转换为 'O' 需要执行的 最少 操作次数。 示例 1…
2
题型
7
代码语言
3
相关题
当前训练重点
简单 · 贪心·invariant
答案摘要
遍历字符串 ，只要遇到 `'X'`，指针 就直接往后移动三格，并且答案加 ；否则指针 往后移动一格。 时间复杂度 。其中 表示字符串 的长度。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
给你一个字符串 s ，由 n 个字符组成，每个字符不是 'X' 就是 'O' 。
一次 操作 定义为从 s 中选出 三个连续字符 并将选中的每个字符都转换为 'O' 。注意，如果字符已经是 'O' ，只需要保持 不变 。
返回将 s 中所有字符均转换为 'O' 需要执行的 最少 操作次数。
示例 1：
输入：s = "XXX"
输出：1
解释：XXX -> OOO
一次操作，选中全部 3 个字符，并将它们转换为 'O' 。
示例 2：
输入：s = "XXOX" 输出：2 解释：XXOX -> OOOX -> OOOO 第一次操作，选择前 3 个字符，并将这些字符转换为'O'。 然后，选中后 3 个字符，并执行转换。最终得到的字符串全由字符'O'组成。
示例 3：
输入：s = "OOOO"
输出：0
解释：s 中不存在需要转换的 'X' 。
提示：
3 <= s.length <= 1000s[i]为'X'或'O'
解题思路
方法一：贪心
遍历字符串 ，只要遇到 'X'，指针 就直接往后移动三格，并且答案加 ；否则指针 往后移动一格。
时间复杂度 。其中 表示字符串 的长度。
class Solution:
def minimumMoves(self, s: str) -> int:
ans = i = 0
while i < len(s):
if s[i] == "X":
ans += 1
i += 3
else:
i += 1
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Checks if the candidate can apply a greedy strategy for string manipulation.
- question_mark
Evaluates understanding of invariant validation in greedy algorithms.
- question_mark
Assesses the ability to handle edge cases and different string lengths.
常见陷阱
外企场景- error
Forgetting to handle strings with no 'X's properly (result should be zero).
- error
Overcomplicating the solution by trying to track extra state or avoid greedy selection.
- error
Missing the fact that you only need to select three consecutive characters at a time.
进阶变体
外企场景- arrow_right_alt
Allowing variable-length groups of consecutive characters to be selected.
- arrow_right_alt
Modifying the problem so that you can convert one or two characters at a time instead of three.
- arrow_right_alt
Requiring a condition where some 'O's can be converted back into 'X's.