分隔平衡字符串

在一个「平衡字符串」中，‘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".

原题链接🔗：https://leetcode-cn.com/problems/split-a-string-in-balanced-strings/

解答

• 因为对字符串进行分隔，被分割后的字符串组合起来就是原有的字符串。
• 它分割成尽可能多的平衡字符串，那么如果遇到分隔的点就要分隔。
• R和L的数量是相同的，猜测可能有的结果：
  • RL
  • LR
  • RRLL
  • LLRR
  • … 依次类推

代码-Java

public class Solution {

    public static void main(String[] args) {
        List<String> testers = Arrays.asList("RLRRLLRLRL", "RLLLLRRRLR", "LLLLRRRR");
        testers.forEach(s -> System.out.println(balancedStringSplit(s)));
    }

    static public int balancedStringSplit(String s) {
        if (s == null || s.isEmpty()) {
            return 0;
        }
        int rc = 0;
        int lc = 0;
        //  方便统计有哪些字符串用的
        int beginIndex = 0;

        // 出现平衡字符串次数
        int count = 0;
        for (int currentIndex = 1; currentIndex <= s.length(); currentIndex++) {
            if (s.charAt(currentIndex - 1) == 'R') {
                rc += 1;
            }
            if (s.charAt(currentIndex - 1) == 'L') {
                lc += 1;
            }
            // 代表出现了相同次数的L和R
            if (rc == lc && rc != 0) {
                count++;
                rc = 0;
                lc = 0;
                System.out.println(s.substring(beginIndex, currentIndex));
                beginIndex = currentIndex;
            }
        }
        return count;
    }
}

运行结果

RL
RRLL
RL
RL
4
RL
LLLRRR
LR
3
LLLLRRRR
1

Process finished with exit code 0

其他思路?

利用一个变量num记录’L’(‘R’)的数量，遍历字符串s，如果字符为’L’(‘R’)，则num++，否则num-- 当num为0时，之前出现的’L’和’R’的数量必定相等，此时将记录子串数量的res++，遍历完后返回res