1221-分割平衡字符串

平衡字符串 中，'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 是一个 平衡 字符串

方法一：贪心

根据题意，对于一个平衡字符串 s，若 s 能从中间某处分割成左右两个子串，若其中一个是平衡字符串，则另一个的 L 和 R 字符的数量必然是相同的，所以也一定是平衡字符串。

为了最大化分割数量，我们可以不断循环，每次从 s 中分割出一个最短的平衡前缀，由于剩余部分也是平衡字符串，我们可以将其当作 s 继续分割，直至 s 为空时，结束循环。

代码实现中，可以在遍历 s 时用一个变量 d 维护 L 和 R 字符的数量之差，当 d=0 时就说明找到了一个平衡字符串，将答案加一。

[sol1-C++]

class Solution {
public:
    int balancedStringSplit(string s) {
        int ans = 0, d = 0;
        for (char ch : s) {
            ch == 'L' ? ++d : --d;
            if (d == 0) {
                ++ans;
            }
        }
        return ans;
    }
};

[sol1-Java]

class Solution {
    public int balancedStringSplit(String s) {
        int ans = 0, d = 0;
        for (int i = 0; i < s.length(); ++i) {
            char ch = s.charAt(i);
            if (ch == 'L') {
                ++d;
            } else {
                --d;
            }
            if (d == 0) {
                ++ans;
            }
        }
        return ans;
    }
}

[sol1-C#]

public class Solution {
    public int BalancedStringSplit(string s) {
        int ans = 0, d = 0;
        foreach (char ch in s) {
            if (ch == 'L') {
                ++d;
            } else {
                --d;
            }
            if (d == 0) {
                ++ans;
            }
        }
        return ans;
    }
}

[sol1-Python3]

class Solution:
    def balancedStringSplit(self, s: str) -> int:
        ans, d = 0, 0
        for ch in s:
            if ch == 'L':
                d += 1
            else:
                d -= 1
            if d == 0:
                ans += 1
        return ans

[sol1-Golang]

func balancedStringSplit(s string) (ans int) {
    d := 0
    for _, ch := range s {
        if ch == 'L' {
            d++
        } else {
            d--
        }
        if d == 0 {
            ans++
        }
    }
    return
}

[sol1-JavaScript]

var balancedStringSplit = function(s) {
    let ans = 0, d = 0;
    for (let i = 0; i < s.length; ++i) {
        const ch = s[i];
        if (ch === 'L') {
            ++d;
        } else {
            --d;
        }
        if (d === 0) {
            ++ans;
        }
    }
    return ans;
};

[sol1-C]

int balancedStringSplit(char* s) {
    int ans = 0, d = 0;
    for (int i = 0; s[i]; i++) {
        s[i] == 'L' ? ++d : --d;
        if (d == 0) {
            ++ans;
        }
    }
    return ans;
}

复杂度分析

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

• 空间复杂度：O(1)。只需要常数的空间存放若干变量。