题目描述

在一个 平衡字符串 中，’L’ 和 ‘R’ 字符的数量是相同的。

给出一个平衡字符串 s，请你将它分割成尽可能多的平衡字符串。

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

样例

输入：s = "RLRRLLRLRL"
输出：4
解释：s 可以分割为 "RL", "RRLL", "RL", "RL", 每个子字符串中都包含相同数量的 'L' 和 'R'。

输入：s = "RLLLLRRRLR"
输出：3
解释：s 可以分割为 "RL", "LLLRRR", "LR", 每个子字符串中都包含相同数量的 'L' 和 'R'。

输入：s = "LLLLRRRR"
输出：1
解释：s 只能保持原样 "LLLLRRRR"。

限制

• 1 <= s.length <= 1000
• s[i] = 'L' or 'R'

算法

(线性扫) $O(n)$

1. 用一个变量记录当前未匹配的 L 的数量，如果这个数量到了 0，则答案加 1。

时间复杂度

• 只扫描一次数组，故时间复杂度为 $O(n)$。

空间复杂度

• 只使用常数的额外空间。

C++ 代码

class Solution {
public:
    int balancedStringSplit(string s) {
        int x = 0, ans = 0;
        for (char c: s) {
            if (c == 'L')
                x++;
            else
                x--;

            if (x == 0)
                ans++;
        }
        return ans;
    }
};