leetcode1221. 分割平衡字符串

LeetCode系列文章

一、题目描述

  在一个平衡字符串中，${}^{\prime }{L}^{\prime }$ 和 ${}^{\prime }{R}^{\prime }$ 字符的数量是相同的。
 
  给你一个平衡字符串 $s$，请你将它分割成尽可能多的平衡字符串。
 
  返回可以通过分割得到的平衡字符串的最大数量。
 
  注意：分割得到的每个字符串都必须是平衡字符串，且分割得到的平衡字符串是原字符串的连续子串。

二、示例

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

三、主体思路

  该题目实际考察的是贪心算法，也就是在求解问题时，总是做出在当前看来是最好的选择。对于该题目来说，我们在遍历平衡字符串进行分割时，一旦发现一个子平衡字符串就应该立即将其分割出来。
 
  比如对于平衡字符串 “RLRRLLRLRL”，我们在遍历时可以遍历到 “RL” 就进行分割，也可以遍历到 “RLRRLL” 再进行分割，因为 “RL” 和 “RLRRLL” 都是平衡字符串。

  但题目要求的是分割得到的平衡字符串的最大数量，因此我们在遍历到 “RL” 时就应该进行分割，此时后面的 “RRLL” 就可以分割成另一个平衡字符串。按照该方法遍历所给平衡字符串，最终就能够分割后可得到的平衡字符串的最大数量。
 
  需要注意的是，所给平衡字符串最终一定会被分割为若干个完整的子平衡字符串，而不会出现某些剩余字符无法组成一个平衡字符串的情况。因为当你从平衡字符串当中分割出一个子平衡字符串后，剩下的字符串当中R和L的数量也一定是相等的，因此该字符串也是一个平衡字符串。
 
如下图所示：

四、代码实现

在分析问题时所说的分割字符串只是为了方便理解，实际在解题时并不需要真正对字符串进行分割。

• 我们可以定义一个level变量，该变量的初始值设置为0。
• 在变量平衡字符串的过程中，如果遍历到的字符是R，则对level进行自增，如果遍历到的字符是L，则对level进行自减。（反过来也可以）
• 除了level初始值的设定，在遍历过程中level的值有几次变为0，则说明该平衡字符串最多可以分割为多少个子平衡字符串。

 
动图演示：

代码如下：