Easy

题目描述

平衡字符串是指具有相等数量 ‘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. 贪心策略：我们尽可能早地分割字符串，一旦找到一个平衡的子字符串就立即分割。这样能保证得到最多的平衡子字符串数量。

  2. 平衡计数器：使用一个计数器来跟踪当前子字符串的平衡状态：

    • 遇到 ‘R’ 时计数器 +1
    • 遇到 ‘L’ 时计数器 -1
    • 当计数器为 0 时，说明从上一个分割点到当前位置的子字符串是平衡的

  3. 算法流程：

    • 从左到右遍历字符串
    • 维护一个平衡计数器和结果计数器
    • 每当平衡计数器归零时，结果计数器 +1
    • 最终返回结果计数器的值

为什么贪心策略是正确的？ 因为如果我们可以在位置 i 分割得到一个平衡子字符串，那么延后分割不会增加总的平衡子字符串数量，反而可能减少后续的分割机会。

代码实现

class Solution {
public:
    int balancedStringSplit(string s) {
        int balance = 0, count = 0;
        for (char c : s) {
            balance += (c == 'R') ? 1 : -1;
            if (balance == 0) {
                count++;
            }
        }
        return count;
    }
};

class Solution:
    def balancedStringSplit(self, s: str) -> int:
        balance = 0
        count = 0
        for c in s:
            balance += 1 if c == 'R' else -1
            if balance == 0:
                count += 1
        return count

public class Solution {
    public int BalancedStringSplit(string s) {
        int balance = 0, count = 0;
        foreach (char c in s) {
            balance += (c == 'R') ? 1 : -1;
            if (balance == 0) {
                count++;
            }
        }
        return count;
    }
}

/**
 * @param {string} s
 * @return {number}
 */
var balancedStringSplit = function(s) {
    let count = 0;
    let balance = 0;
    
    for (let i = 0; i < s.length; i++) {
        if (s[i] === 'R') {
            balance++;
        } else {
            balance--;
        }
        
        if (balance === 0) {
            count++;
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历字符串一次，其中 n 是字符串长度
空间复杂度O(1)只使用了常数个额外变量

相关题目