分隔平衡字符串

分隔平衡字符串

马草原 477 2022-06-11

分隔平衡字符串

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