LeetCode 1221 分割平衡字符串：贪心策略与「±1 计分」判定的完整题解（LogicStack-LeetCode 刷穿系列）

导读

本文基于 LogicStack-LeetCode 仓库中 LeetCode/1221-1230/1221. 分割平衡字符串（简单）.md 的官方题解展开，系统讲解 LeetCode 1221「分割平衡字符串」的贪心解法。读完本文，你将掌握把「两类元素数量相等」的成对结构统计转化为「±1 得分归零」数学判定的通用技巧，理解并独立证明「每次取最小分割点即可得到最多分割数」的贪心正确性，并拿到 Java、C++、Python、TypeScript 四种语言的可直接提交代码。

---

题目描述

在一个平衡字符串中，'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 中 'L' 与 'R' 的数量相等，这保证了分割方案一定存在，我们只需要追求「分割段数最多」。

---

基本分析：把成对结构统计转化为数学判定

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

一个合法的 LR 子串满足 L 字符和 R 字符数量相等。常规检查一个字符串是否为合格的 LR 子串，可以使用 $O(n)$ 的遍历方式，或者使用记录前缀信息的数据结构（例如前缀计数数组、哈希表等）。

但对于「两类元素成对抵消」的结构统计，更好的方式是转换为数学判定：

使用 1 来代指 L 得分，使用 -1 来代指 R 得分。

这样，一个子串为合格 LR 子串的充要条件为：

整个 LR 子串的总得分为 $0$。

把"统计两类字符数量"转换成"维护一个可正可负的整型得分"，好处在于：

1. 判断过程从"分别统计两个计数再比较"退化为"只维护一个累计值"，省去了一半的状态；
2. 无需额外的哈希表或前缀数组，空间占用为 $O(1)$；
3. 得分归零的判定天然支持"边扫描边判断"，非常适合单次遍历的贪心/双指针流程。

该技巧的通用性：延伸到任意成对结构统计

这种「成对结构用 ±1 计分、归零即合法」的方式，最早在仓库的 LeetCode/301-310/301. 删除无效的括号（困难）.md 题解中详细讲解过。

在 301 题中，同样令左括号得分为 $1$、右括号得分为 $-1$，并由此得到两条性质：

1. 对于一个合法的括号方案而言，必然有最终得分为 $0$；
2. 搜索过程中不会出现得分值为负数的情况（当且仅当某个前缀中"右括号数量大于左括号数量"时会出现负数，此时不是合法方案）。

这两条性质正是 301 题回溯搜索剪枝的核心依据。可见，+1 / -1 计分法可以自然延伸到括号、左右配平、正负抵消等任意成对结构元素统计的题目中去，是值得沉淀的通解模板。

---

贪心策略：每一次都从最小分割点下手

回到本题，题目要求分割出的 LR 子串尽可能多，直观上应该是尽可能让每个分割串尽可能短——因为段数 = 总长度分配出的段数，段越短，可分的段数自然越多。

但"直观正确"不等于"数学正确"，尤其是贪心算法，必须给出严谨的正确性证明。原题解使用归纳法完成了这一证明，这也是本题最有价值的学习点。

归纳法证明

首先题目数据保证给定的 s 本身是合法的 LR 子串。

假设一： 从 $[0...a]$ 可以从 s 中分割出长度最小的 LR 子串。

假设二： 从 $[0...b]$ 能够分割出长度更大的 LR 子串（即 $a \le b$）。

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

证明分两步：

第一步：合法性不丢失。

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

• 左端：$[0...a]$ 与 $[0...b]$ 都是合法 LR 子串（$a$ 本身就是一个合法分割点）；
• 右端：由于 $[0...b]$ 是合法子串，且 $a \le b$，那么 $[a+1...b]$ 作为"两个合法子串之差"，其总得分同样为 $0$，因此 $[a+1...n-1]$ 依然是一个合法 LR 子串，可继续分割。

第二步：后续可分割数量不减少。

从 b 分割后的剩余部分长度小于从 a 分割后的剩余部分，同时由 b 分割后的剩余部分会被由 a 分割后的剩余部分所严格覆盖（因为 $[b+1...n-1] \subset [a+1...n-1]$）。

因此，「对 a 分割的剩余部分再分割所得的子串数量」至少与「从 b 点分割的剩余部分再分割所得的子串数量」相等（不会变少）。

综合两步，我们证明了：对于首次分割，将任意合格分割点调整为最小分割点，结果不会变得更差（当 $a < b$ 时还会更好）。

同时，由于首次分割后的剩余部分仍为合格的 LR 子串，因此归纳分析所依赖的结构没有发生改变，可以将上述推理分析推广到**每一个决策的回合（新边界）**中。

至此，归纳完成：

只要每一次都从最小分割点进行分割，就可以得到最优解。

这个证明框架非常典型：先证"某一步的局部最优调整不破坏全局合法性"，再证"剩余子问题结构不变、可递归套用"，最后归纳出全局最优。这种"调整法 + 归纳法"的组合，是证明贪心正确性的标准范式，也出现在仓库 Index/贪心算法.md 索引下的多道题解中。

---

算法流程与多语言实现

依据上述贪心策略，算法流程如下：

1. 初始化指针 i = 0，答案计数器 ans = 0；
2. 对每个子串起点 i，令 j = i + 1，初始化 score 为 s[i] 的得分（'L' 记 +1，'R' 记 -1）；
3. 不断推进 j 并累加得分，直到 score == 0，此时 [i, j) 即为从当前最小分割点切出的合法 LR 子串；
4. 令 i = j，ans++，进入下一段；
5. 返回 ans。

Java 代码

class Solution {
    public int balancedStringSplit(String s) {
        char[] cs = s.toCharArray();
        int n = cs.length, 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;
    }
}

C++ 代码

class Solution {
public:
    int balancedStringSplit(string s) {
        int n = s.size(), ans = 0;
        for (int i = 0; i < n; ) {
            int j = i + 1;
            int score = (s[i] == 'L') ? 1 : -1;
            while (j < n && score != 0) score += (s[j++] == 'L') ? 1 : -1;
            i = j;
            ans++;
        }
        return ans;
    }
};

Python 代码

class Solution:
    def balancedStringSplit(self, s: str) -> int:
        ans, i, n = 0, 0, len(s)
        while i < n:
            j = i + 1
            score = 1 if s[i] == 'L' else -1
            while j < n and score != 0:
                score += 1 if s[j] == 'L' else -1
                j += 1
            i = j
            ans += 1
        return ans

TypeScript 代码

function balancedStringSplit(s: string): number {
    let n = s.length, ans = 0;
    for (let i = 0; i < n; ) {
        let j = i + 1;
        let score = s[i] === 'L' ? 1 : -1;
        while (j < n && score !== 0) score += s[j++] === 'L' ? 1 : -1;
        i = j;
        ans++;
    }
    return ans;
};

复杂度分析

• 时间复杂度： $O(n)$。每个字符恰好被内部指针 j 扫描一次，外层 i 直接跳到 j，全程单遍线性扫描。
• 空间复杂度：
  • Java 版本调用 toCharArray 会拷贝新数组进行返回（为遵循 String 的不可变原则），因此使用 toCharArray 的空间复杂度为 $O(n)$；
  • 若改用 charAt 按索引取字符，空间复杂度为 $O(1)$；
  • C++ / Python / TypeScript 版本均为 $O(1)$ 额外空间。

实践提示：在 Java 中，当追求极致空间时可将 s.toCharArray() 换成循环内 s.charAt(i) / s.charAt(j) 访问；当追求更快的常数时间时，toCharArray 的连续数组访问通常更友好。两者时间复杂度相同，仅空间常数有差异。

---

手动推演：以四个示例验证算法

以示例 1 s = "RLRRLLRLRL" 为例逐步推演：

• 起点 i = 0：R 记 -1，向右扫描：R(-1) → L(0)，得分为 0，切出 "RL"，ans = 1；
• 起点 i = 2：R 记 -1，R(-2) → L(-1) → L(0)，切出 "RRLL"，ans = 2；
• 起点 i = 6：R(-1) → L(0)，切出 "RL"，ans = 3；
• 起点 i = 8：R(-1) → L(0)，切出 "RL"，ans = 4。

最终得到 4，与官方输出一致。其余三个示例同理，"RLLLLRRRLR" 输出 3、"LLLLRRRR" 输出 1、"RLRRRLLRLL" 输出 2，均与题目给定结果吻合，可作为提交前的自测用例。

---

仓库延伸阅读

本题在仓库的知识索引体系中位于两处，可对照查阅同类题目：

• Index/贪心算法.md：贪心类题解汇总，包含 11、45、179、334、881 等经典贪心题目；
• Index/双指针.md：双指针类题解汇总，包含 3、15、76、424 等双指针题目。

「±1 计分」这一通解技巧的完整推导可见：

• LeetCode/301-310/301. 删除无效的括号（困难）.md：同一计分法在括号成对结构中的剪枝应用；
• Index/括号问题.md：括号类题目的索引目录，收录 20、22、32、301、678 等题。

仓库根目录的 README.md 说明了这是一个日更的算法题解仓库，全部题解按 Tag 分类组织，便于按专题系统刷题。

---

总结

LeetCode 1221「分割平衡字符串」是一道将"成对结构统计"与"贪心正确性证明"结合得非常巧妙的简单题：

1. 建模层面：用 L = +1、R = -1 的得分法，把"两类字符数量相等"转化为"区间总得分为 0"，让合法性判断退化为单变量维护；
2. 算法层面：贪心"每次切出最短合法段"，配合归纳法证明其最优性，是一次完整的"猜想—证明—实现"闭环；
3. 工程层面：四种主流语言的实现均可在 $O(n)$ 时间内完成，Java 侧还可根据对空间的要求在 toCharArray 与 charAt 之间选择。

掌握这道题的「±1 计分 + 归纳证明贪心」组合拳，你就能在括号、左右配平、正负抵消等更多成对结构统计问题中举一反三。