LC 1221. 分割平衡字符串

题目描述

这是 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 是一个 平衡 字符串

---

基本分析

题目确保了 s 为一个平衡字符串，即必然能分割成若干个 LR 子串。

一个合法的 LR 子串满足 L 字符和 R 字符数量相等，常规检查一个字符串是否为合格的 LR 子串可以使用 $O(n)$ 的遍历方式，可以使用记录前缀信息的数据结构，而对于成对结构的元素统计，更好的方式是转换为数学判定，使用 1 来代指 L 得分，使用 -1 来代指 R 得分。

那么一个子串为合格 LR 子串的充要条件为 整个 LR 子串的总得分为 $0$。

这种方式最早应该在 (题解) 301. 删除无效的括号 详细讲过，可延伸到任意的成对结构元素统计题目里去。

---

贪心

回到本题，题目要求分割的 LR 子串尽可能多，直观上应该是尽可能让每个分割串尽可能短。

我们使用「归纳法」来证明该猜想的正确性。

首先题目数据保证给定的 s 本身是合法的 LR 子串，假设从 $[0…a]$ 可以从 s 中分割出 长度最小 的 LR 子串，而从 $[0…b]$ 能够分割出 长度更大 的 LR 子串（即 a <= b )。

我们来证明起始时（第一次分割）「将从 b 分割点将 s 断开」调整为「从 a 分割点将 s 断开」结果不会变差：

1. 从 b 点首次分割调整为从 a 点首次分割，两种分割形式分割点两端仍为合法 LR 子串，因此不会从“有解”变成“无解”；

2. 从 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)$
• 空间复杂度：调用 toCharArray 会拷贝新数组进行返回（为遵循 String 的不可变原则），因此使用 toCharArray 复杂度为 $O(n)$，使用 charAt 复杂度为 $O(1)$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1221 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。