力扣 1221. 分割平衡字符串

题目描述

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

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

注意：分割得到的每个 字符串 都必须是平衡字符串，且分割得到的平衡字符串是原平衡字符串的连续子串。

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

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

 输入：s = "RLRRRLLRLL"
输出：2
解释：s 可以分割为 "RL"、"RRRLLRLL" ，每个子字符串中都包含相同数量的 'L' 和 'R' 。  

提示：

• 1 <= s.length <= 1000
• s[i] = ‘L’ 或 ‘R’
• s 是一个 平衡 字符串

解决方案

方法一：贪心

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

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

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

代码

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;
    }
};  

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;
    }
}  

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;
    }
}  

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  

Golang

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

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;
};  

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)。只需要常数的空间存放若干变量。

本文作者：力扣

声明：本文归“力扣”版权所有，如需转载请联系