[数据结构与算法]【LeetCode每日一题】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 是一个 平衡 字符串

题解：

要求：将一个平衡字符串分解为若干子平衡字符串，并保证其数量为最大
理解：若平衡字符串分割为两部分，其中一个为平衡字符串，则另一个也一定是平衡字符串，因为被分割掉数量对称的字符 L 和 R之后，剩余的字符 L 和 R的数量依然是对称的。
推断：假设我们已经获得最大数量的子平衡字符串，那么它必然是由一个个顺序的不可再被分割的子平衡字符串连接构成
结论：我们只需按字符串从头到尾的顺序，依次找出不可再分割子平衡字符串即可

方法一：（很像括号匹配算法）

class Solution {
    public int balancedStringSplit(String s) {
      // 对 L 和 R 进行计数，遇到 L 加一，遇到 R 减一，flag==0时，counter++; 
      int flag = 0, counter = 0;
      for (int i = 0; i < s.length(); i++) {
        flag += s.charAt(i) == 'L' ? 1 : -1 ;
        if (flag == 0){
          ++counter;
        }
      }
      return counter;
    }
}    

方法二（认证小白做法）：

class Solution {
    public int balancedStringSplit(String s) {
        int count = 0;
// 1. 利用（String）Obj.toCharArray() 把 String cast to char[]
        char[] chars = s.toCharArray();
// 2. 利用 public static char[] copyOfRange(char[] original, int from, int to) 对字符数组进行分割
        while (chars.length != 0){
            int r = 0, l= 0;
            for (int i=0; i<chars.length; ++i){
                if (chars[i] == 'R'){
                    ++r;
                }else {
                    ++l;
                }
                if (r == l){
                    chars = Arrays.copyOfRange(chars, i+1, chars.length);
                    break;
                }
            }
            ++count;
        }
        return count;
    }
}    

时间复杂度：O(n)，其中n为字符串s的长度
空间复杂度：O(1)，因为局部变量和参数的占用空间并不会随着n的大小而改变

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