1221. 分割平衡字符串

🟢   🔖  贪心 字符串 计数  🔗 力扣 LeetCode

题目

Balanced strings are those that have an equal quantity of 'L' and 'R' characters.

Given a balanced string s, split it into some number of substrings such that:

• Each substring is balanced.

Return the maximum number of balanced strings you can obtain.

Example 1:

Input: s = "RLRRLLRLRL"

Output: 4

Explanation: s can be split into "RL", "RRLL", "RL", "RL", each substring contains same number of 'L' and 'R'.

Example 2:

Input: s = "RLRRRLLRLL"

Output: 2

Explanation: s can be split into "RL", "RRRLLRLL", each substring contains same number of 'L' and 'R'.

Note that s cannot be split into "RL", "RR", "RL", "LR", "LL", because the 2nd and 5th substrings are not balanced.

Example 3:

Input: s = "LLLLRRRR"

Output: 1

Explanation: s can be split into "LLLLRRRR".

Constraints:

• 2 <= s.length <= 1000
• s[i] is either 'L' or 'R'.
• s is a balanced string.

题目大意

平衡字符串 中，'L' 和 'R' 字符的数量是相同的。

给你一个平衡字符串 s，请你将它分割成尽可能多的子字符串，并满足：

• 每个子字符串都是平衡字符串。

返回可以通过分割得到的平衡字符串的 最大数量。

示例 1：

输入： s = "RLRRLLRLRL"

输出： 4

解释： s 可以分割为 "RL"、"RRLL"、"RL"、"RL" ，每个子字符串中都包含相同数量的 'L' 和 'R' 。

示例 2：

输入： s = "RLRRRLLRLL"

输出： 2

解释： s 可以分割为 "RL"、"RRRLLRLL"，每个子字符串中都包含相同数量的 'L' 和 'R' 。

注意，s 无法分割为 "RL"、"RR"、"RL"、"LR"、"LL" 因为第 2 个和第 5 个子字符串不是平衡字符串。

示例 3：

输入： s = "LLLLRRRR"

输出： 1

解释： s 只能保持原样 "LLLLRRRR" 。

提示：

• 2 <= s.length <= 1000
• s[i] = 'L' 或 'R'
• s 是一个 平衡 字符串

解题思路

1. 使用一个计数器 count 来记录当前分割字符串的平衡状态：
   • 遇到 'R' 时，count--。
   • 遇到 'L' 时，count++。
2. 当 count == 0 时，说明我们找到一个平衡字符串，计数器 res++。
3. 遍历字符串，最终返回 res 即为分割出的平衡字符串的个数。

复杂度分析

• 时间复杂度：O(n)，遍历字符串 s 一次。
• 空间复杂度：O(1)，只使用了常量空间存储 count 和 res。

代码

/**
 * @param {string} s
 * @return {number}
 */
var balancedStringSplit = function (s) {
	let count = 0; // 记录当前的平衡状态
	let res = 0; // 记录平衡字符串的数量

	for (let char of s) {
		if (char === 'R') {
			count--; // 遇到 'R'，减少平衡值
		} else {
			count++; // 遇到 'L'，增加平衡值
		}
		if (count === 0) {
			res++; // 平衡字符串结束，计数加 1
		}
	}

	return res;
};

相关题目

题号	标题	题解	标签	难度	力扣
2788	按分隔符拆分字符串		数组 字符串	🟢	🀄️ 🔗