题目描述
这是 LeetCode 上的 1221. 分割平衡字符串 ，难度为 简单。
Tag : 「贪心」、「双指针」
在一个 平衡字符串 中，'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 为一个平衡字符串，即必然能分割成若干个 LR 子串。
一个合法的 LR 子串满足 L 字符和 R 字符数量相等，常规检查一个字符串是否为合格的 LR 子串可以使用 O(n)O(n) 的遍历方式，可以使用记录前缀信息的数据结构，而对于成对结构的元素统计，更好的方式是转换为数学判定，使用 1 来代指 L 得分，使用 -1 来代指 R 得分。
那么一个子串为合格 LR 子串的充要条件为 整个 LR 子串的总得分为 00。
这种方式最早应该在 (题解) 301. 删除无效的括号 详细讲过，可延伸到任意的成对结构元素统计题目里去。
贪心
回到本题，题目要求分割的 LR 子串尽可能多，直观上应该是尽可能让每个分割串尽可能短。
我们使用「归纳法」来证明该猜想的正确性。
首先题目数据保证给定的 s 本身是合法的 LR 子串，假设从 [0...a][0...a] 可以从 s 中分割出 长度最小 的 LR 子串，而从 [0...b][0...b] 能够分割出 长度更大 的 LR 子串（即 a <= b )。
我们来证明起始时（第一次分割）「将从 b 分割点将 s 断开」调整为「从 a 分割点将 s 断开」结果不会变差：
- 从
b点首次分割调整为从a点首次分割，两种分割形式分割点两端仍为合法LR子串，因此不会从“有解”变成“无解”； - 从
b分割后的剩余部分长度小于从a分割后的剩余部分，同时由b分割后的剩余部分会被由a分割后的剩余部分所严格覆盖，因此「对a分割的剩余部分再分割所得的子串数量」至少 与「从b点分割的剩余部分再分割所得的子串数量」相等（不会变少）。
至此，我们证明了对于首次分割，将任意合格分割点调整为最小分割点，结果不会变得更差（当 a < b 时还会更好）。
同时，由于首次分割后的剩余部分仍为合格的 LR 子串，因此归纳分析所依赖的结构没有发生改变，可以将上述的推理分析推广到每一个决策的回合（新边界）中。
至此，我们证明了只要每一次都从最小分割点进行分割，就可以得到最优解。
代码：
class Solution { public int balancedStringSplit(String s) { char[] cs = s.toCharArray(); int n = cs.length; int ans = 0; for (int i = 0; i < n; ) { int j = i + 1, score = cs[i] == 'L' ? 1 : -1; while (j < n && score != 0) score += cs[j++] == 'L' ? 1 : -1; i = j; ans++; } return ans; } } 复制代码
- 时间复杂度：O(n)O(n)
- 空间复杂度：调用
toCharArray会拷贝新数组进行返回（为遵循String的不可变原则），因此使用toCharArray复杂度为 O(n)O(n)，使用charAt复杂度为 O(1)O(1)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.1221 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
