2027. 转换字符串的最少操作次数

🟢   🔖  贪心 字符串  🔗 力扣 LeetCode

题目

You are given a string s consisting of n characters which are either 'X' or 'O'.

A move is defined as selecting three consecutive characters of s and converting them to 'O'. Note that if a move is applied to the character 'O', it will stay the same.

Return _the minimum number of moves required so that all the characters of _s are converted to'O'.

Example 1:

Input: s = "XXX"

Output: 1

Explanation: XXX -> OOO

We select all the 3 characters and convert them in one move.

Example 2:

Input: s = "XXOX"

Output: 2

Explanation: XXO X -> O OOX -> OOOO

We select the first 3 characters in the first move, and convert them to 'O'.

Then we select the last 3 characters and convert them so that the final string contains all 'O's.

Example 3:

Input: s = "OOOO"

Output: 0

Explanation: There are no 'X's in s to convert.

Constraints:

• 3 <= s.length <= 1000
• s[i] is either 'X' or 'O'.

题目大意

给你一个字符串 s ，由 n 个字符组成，每个字符不是 'X' 就是 'O' 。

一次操作 定义为从 s 中选出 三个连续字符 并将选中的每个字符都转换为 'O' 。注意，如果字符已经是 'O' ，只需要保持 不变 。

返回将 s 中所有字符均转换为 'O' 需要执行的 最少 操作次数。

示例 1：

输入： s = "XXX"

输出： 1

解释： XXX -> OOO

一次操作，选中全部 3 个字符，并将它们转换为 'O' 。

示例 2：

输入： s = "XXOX"

输出： 2

解释： XXO X -> O OOX -> OOOO

第一次操作，选择前 3 个字符，并将这些字符转换为 'O' 。

然后，选中后 3 个字符，并执行转换。最终得到的字符串全由字符 'O' 组成。

示例 3：

输入： s = "OOOO"

输出： 0

解释： s 中不存在需要转换的 'X' 。

提示：

• 3 <= s.length <= 1000
• s[i] 为 'X' 或 'O'

解题思路

1. 初始化变量 moves 表示操作次数为 0。

2. 遍历字符串 s：

   • 遇到 'X' 时，需要一次操作。
   • 每次操作将当前 'X' 及其后两个字符变成 'O'，因此可以跳过接下来的两个字符（即 i += 2）。

3. 遍历结束后，返回所需的操作次数 moves。

复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串的长度， 遍历字符串一次。

• 空间复杂度：O(1)，只使用常量空间。

代码

/**
 * @param {string} s
 * @return {number}
 */
var minimumMoves = function (s) {
	let moves = 0;
	for (let i = 0; i < s.length; i++) {
		if (s[i] == 'X') {
			moves++;
			i += 2; // 跳过接下来的两个字符
		}
	}
	return moves;
};

相关题目

题号	标题	题解	标签	难度	力扣
2976	转换字符串的最小成本 I		图 数组 字符串 1+	🟠	🀄️ 🔗
2977	转换字符串的最小成本 II		图 字典树 数组 3+	🔴	🀄️ 🔗