1221. 分割平衡字符串
1221. 分割平衡字符串
题目
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
是一个 平衡 字符串
解题思路
- 使用一个计数器
count
来记录当前分割字符串的平衡状态:- 遇到
'R'
时,count--
。 - 遇到
'L'
时,count++
。
- 遇到
- 当
count == 0
时,说明我们找到一个平衡字符串,计数器res++
。 - 遍历字符串,最终返回
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 | 按分隔符拆分字符串 | 数组 字符串 | 🟢 | 🀄️ 🔗 |