题目描述
思路解析
一句话答案：LeetCode 1221 分割平衡字符串：一遍扫维护差值，遇 L 加一遇 R 减一，差值一归零就切一段计数加一——能切就切段数最多，时间 O(n)、空间 O(1)。
怎样算平衡串，最多能切几段
先把「平衡」说清楚：一个由 L 和 R 组成的串，里头 L 的个数和 R 的个数一样多，就叫平衡。题目给的整串本身已经平衡，要你把它剪成若干段，每一段单独拿出来也得平衡——L 和 R 照样一样多，问最多能剪成几段。题面例子 s='RLRRLLRLRL' 能剪成 4 段，而 s='LLLLRRRR' 怎么剪都只剩一整段。
枚举所有剪法要试多少种
长 n 的串，每两个字符之间都能剪或不剪，剪法有 2^(n−1) 种，一种种试再逐段检查平不平衡，串一长就爆。上回溯或动态规划去搜切点，做的也是同一批重复功。可它们全都没注意到一件更省心的事：判断一段平不平衡，根本不用记它里头具体是哪些字符、排在什么位置。
一个计数器记差值，什么时候能剪
既然只关心一段里 L 和 R 是不是一样多，就用一个计数器记它俩的差：从左往右扫，遇 L 加一、遇 R 减一。这个差从上一个剪口之后开始累计，等它重新回到 0，就说明这一段里加进去的和减掉的抵消干净了，L 和 R 恰好相等，这一段平衡，可以剪。
那要不要一见差值归零就剪？会剪。差值每归零一次，都是一个合法剪口。假如在某个归零处忍着不剪、留到后面，只会把本可以分开的两小段并成一大段，段数只减不增。所以一到 0 就剪，把整串拆成一连串最短的平衡块，段数自然到顶。差值中途变成负数也不用管——串要是从 R 开头，差值会先掉到负的，但只要某一刻回到 0，这一段就配平了，正负号不改结论。
'RLRRLLRLRL' 一位一位过，4 段是怎么落袋的
拿题面的 'RLRRLLRLRL' 走一遍，差值和段数都从 0 起。第 0 位 R，差值 −1；第 1 位 L，差值回 0，剪下 'RL'，段数 1。第 2 位 R 差值 −1、第 3 位 R 差值 −2、第 4 位 L 差值 −1、第 5 位 L 差值回 0，剪下 'RRLL'，段数 2。第 6 位 R 差值 −1、第 7 位 L 差值回 0，剪下 'RL'，段数 3。第 8 位 R 差值 −1、第 9 位 L 差值回 0，剪下 'RL'，段数 4。十位扫完差值停在 0，答案 4 段。
换 'LLLLRRRR' 试：四个 L 把差值推到 4，再四个 R 一路减回，差值直到最后一位才碰到 0，中间从没归零，整串只能算一段，答案 1，和贪心的剪法对得上。
被负号唬住、给计数器加戏、拿回溯兜底，全是白费，还有跑多快
别被差值的负号吓退、以为算错了回头重数——它只是记 L 减 R 的即时落差，正负都行，只有等不等于 0 才有意义。也别为了「看着清楚」另开两个计数器分别数 L 和 R 再逐位比较，一个差值计数器已经把「是否相等」压成「是否为 0」，多一个变量只是多一处能写错的地方。还有人怕贪心不稳，非要回溯验证一圈，其实每个归零位都是铁的合法剪口，能剪就剪不会漏掉更优解。
复杂度上，每个字符只看一次，做一次加减和一次归零判断，时间 O(n)；全程只有差值和段数两个整数，没有额外数组或栈，空间 O(1)。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢一句话:差值遇 L 加一、遇 R 减一,只要差值回到 0 就收下一个平衡段。下面每一帧都在套这句。
总览 · 计数器清零,从最左边开扫：上面这排是 "LRLRLLRRLR" 拆开的 10 个字符,前面有交错,中间也会出现连续的 L 和 R。开扫前把差值计数器清成 0,它代表「目前 L 的个数减 R 的个数」。从最左边第 0 个字符开始,一个一个往右看,差值一回到 0 就收下一段。
读第 0 个 · "L"：扫到第 0 位,是 "L",差值加一,现在差值是 1。绿色这一段是从上一段结尾到这里、还没收走的部分。
暂不成段 · 差值还没归零：差值是 1,不等于 0,说明这一段里 L 和 R 还没配齐,现在收下两边不平衡。所以先不收,把这一位并进当前这段(红框),继续往右扫。
读第 1 个 · "R"：扫到第 1 位,是 "R",差值减一,现在差值是 0。绿色是当前还没收走的这一段。
第 1 段成型 · 收下：差值回到 0 了,说明从上一段结尾到第 1 位这一段里,L 和 R 一样多,是个完整的平衡段。收下这一段,段数变成 1 段,这段(变蓝)收走,下一段从第 2 位重新开始数。
读第 2 个 · "L"：扫到第 2 位,是 "L",差值加一,现在差值是 1。绿色这一段是从上一段结尾到这里、还没收走的部分。
暂不成段 · 差值还没归零：差值是 1,不等于 0,说明这一段里 L 和 R 还没配齐,现在收下两边不平衡。所以先不收,把这一位并进当前这段(红框),继续往右扫。
读第 3 个 · "R"：扫到第 3 位,是 "R",差值减一,现在差值是 0。绿色是当前还没收走的这一段。
第 2 段成型 · 收下：差值回到 0 了,说明从上一段结尾到第 3 位这一段里,L 和 R 一样多,是个完整的平衡段。收下这一段,段数变成 2 段,这段(变蓝)收走,下一段从第 4 位重新开始数。
读第 4 个 · "L"：扫到第 4 位,是 "L",差值加一,现在差值是 1。绿色这一段是从上一段结尾到这里、还没收走的部分。
暂不成段 · 差值还没归零：差值是 1,不等于 0,说明这一段里 L 和 R 还没配齐,现在收下两边不平衡。所以先不收,把这一位并进当前这段(红框),继续往右扫。
读第 5 个 · "L"：扫到第 5 位,是 "L",差值加一,现在差值是 2。绿色这一段是从上一段结尾到这里、还没收走的部分。
暂不成段 · 差值还没归零：差值是 2,不等于 0,说明这一段里 L 和 R 还没配齐,现在收下两边不平衡。所以先不收,把这一位并进当前这段(红框),继续往右扫。
读第 6 个 · "R"：扫到第 6 位,是 "R",差值减一,现在差值是 1。绿色是当前还没收走的这一段。
暂不成段 · 差值还没归零：差值是 1,不等于 0,说明这一段里 L 和 R 还没配齐,现在收下两边不平衡。所以先不收,把这一位并进当前这段(红框),继续往右扫。
读第 7 个 · "R"：扫到第 7 位,是 "R",差值减一,现在差值是 0。绿色是当前还没收走的这一段。
第 3 段成型 · 收下：差值回到 0 了,说明从上一段结尾到第 7 位这一段里,L 和 R 一样多,是个完整的平衡段。收下这一段,段数变成 3 段,这段(变蓝)收走,下一段从第 8 位重新开始数。
读第 8 个 · "L"：扫到第 8 位,是 "L",差值加一,现在差值是 1。绿色这一段是从上一段结尾到这里、还没收走的部分。
暂不成段 · 差值还没归零：差值是 1,不等于 0,说明这一段里 L 和 R 还没配齐,现在收下两边不平衡。所以先不收,把这一位并进当前这段(红框),继续往右扫。
读第 9 个 · "R"：扫到第 9 位,是 "R",差值减一,现在差值是 0。绿色是当前还没收走的这一段。
第 4 段成型 · 收下：差值回到 0 了,说明从上一段结尾到第 9 位这一段里,L 和 R 一样多,是个完整的平衡段。收下这一段,段数变成 4 段,这段(变蓝)收走,下一段从第 10 位重新开始数。
完成 · 答案 4 段：10 个字符全扫完,差值正好停在 0,整串被切成 4 段:开头两段各是一个 "LR",中间攒出一个 "LLRR",最后又一个 "LR"。每段 L 和 R 都一样多,段数最多就是 4,答案站得住。
边界都一个套路:差值每归零一次就多一段;像 "LLLLRRRR" 中途从不归零,只能当一整段。
面试重点:能切就切所以最优、计数方向不影响结论、时间 O(n) 空间 O(1)。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def balancedStringSplit(self, s: str) -> int: ans = l = 0 for c in s: if c == 'L': l += 1 else: l -= 1 if l == 0: ans += 1 return ans复杂度
- 时间：O(n)，n 为字符串长度。从左到右每个字符只看一遍,做一次加减和一次「是否归零」判断,整体是线性扫描
- 空间：O(1)，自始至终只用了差值计数器和段数计数器两个整数,没有额外的数组或栈,峰值占用是常数
易错点
面试追问把动画讲成自己的话
追问为什么贪心每次差值归零就切,一定能得到最多的段数?
追问计数器记「L 的个数减 R」和记「R 减 L」有区别吗?
追问这题的时间和空间复杂度是多少?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
使每位学生都有座位的最少移动次数
LeetCode 2037 · 简单 · 沿着 贪心套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题