跳至主要內容

1221. 分割平衡字符串


1221. 分割平衡字符串

🟢   🔖  贪心 字符串 计数  🔗 力扣open in new window LeetCodeopen in new window

题目

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),只使用了常量空间存储 countres

代码

/**
 * @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按分隔符拆分字符串数组 字符串🟢🀄️open in new window 🔗open in new window