分割平衡字符串 图解题解
这道题到底在问什么
- 输入
- s = "RLRRLLRLRL"
- 输出
- 4
- 输入
- s = "LLLLRRRR"
- 输出
- 1
- 输入
- 本节演示 s = "LRLRLLRRLR"
- 输出
- 4
先想最直接的笨办法
上面这排是 "LRLRLLRRLR" 拆开的 10 个字符,前面有交错,中间也会出现连续的 L 和 R。开扫前把差值计数器清成 0,它代表「目前 L 的个数减 R 的个数」。从最左边第 0 个字符开始,一个一个往右看,差值一回到 0 就收下一段。（动画第 4 步）
最优解：一步一步想明白
- 3记牢一句话:差值遇 L 加一、遇 R 减一,只要差值回到 0 就收下一个平衡段。下面每一帧都在套这句。
- 4上面这排是 "LRLRLLRRLR" 拆开的 10 个字符,前面有交错,中间也会出现连续的 L 和 R。开扫前把差值计数器清成 0,它代表「目前 L 的个数减 R 的个数」。从最左边第 0 个字符开始,一个一个往右看,差值一回到 0 就收下一段。
- 5扫到第 0 位,是 "L",差值加一,现在差值是 1。绿色这一段是从上一段结尾到这里、还没收走的部分。
- 6差值是 1,不等于 0,说明这一段里 L 和 R 还没配齐,现在收下两边不平衡。所以先不收,把这一位并进当前这段(红框),继续往右扫。
- 7扫到第 1 位,是 "R",差值减一,现在差值是 0。绿色是当前还没收走的这一段。
- 8差值回到 0 了,说明从上一段结尾到第 1 位这一段里,L 和 R 一样多,是个完整的平衡段。收下这一段,段数变成 1 段,这段(变蓝)收走,下一段从第 2 位重新开始数。
- 9扫到第 2 位,是 "L",差值加一,现在差值是 1。绿色这一段是从上一段结尾到这里、还没收走的部分。
- 10差值是 1,不等于 0,说明这一段里 L 和 R 还没配齐,现在收下两边不平衡。所以先不收,把这一位并进当前这段(红框),继续往右扫。
- 11扫到第 3 位,是 "R",差值减一,现在差值是 0。绿色是当前还没收走的这一段。
- 12差值回到 0 了,说明从上一段结尾到第 3 位这一段里,L 和 R 一样多,是个完整的平衡段。收下这一段,段数变成 2 段,这段(变蓝)收走,下一段从第 4 位重新开始数。
- 13扫到第 4 位,是 "L",差值加一,现在差值是 1。绿色这一段是从上一段结尾到这里、还没收走的部分。
- 14差值是 1,不等于 0,说明这一段里 L 和 R 还没配齐,现在收下两边不平衡。所以先不收,把这一位并进当前这段(红框),继续往右扫。
- 15扫到第 5 位,是 "L",差值加一,现在差值是 2。绿色这一段是从上一段结尾到这里、还没收走的部分。
- 16差值是 2,不等于 0,说明这一段里 L 和 R 还没配齐,现在收下两边不平衡。所以先不收,把这一位并进当前这段(红框),继续往右扫。
- 17扫到第 6 位,是 "R",差值减一,现在差值是 1。绿色是当前还没收走的这一段。
- 18差值是 1,不等于 0,说明这一段里 L 和 R 还没配齐,现在收下两边不平衡。所以先不收,把这一位并进当前这段(红框),继续往右扫。
- 19扫到第 7 位,是 "R",差值减一,现在差值是 0。绿色是当前还没收走的这一段。
- 20差值回到 0 了,说明从上一段结尾到第 7 位这一段里,L 和 R 一样多,是个完整的平衡段。收下这一段,段数变成 3 段,这段(变蓝)收走,下一段从第 8 位重新开始数。
- 21扫到第 8 位,是 "L",差值加一,现在差值是 1。绿色这一段是从上一段结尾到这里、还没收走的部分。
- 22差值是 1,不等于 0,说明这一段里 L 和 R 还没配齐,现在收下两边不平衡。所以先不收,把这一位并进当前这段(红框),继续往右扫。
- 23扫到第 9 位,是 "R",差值减一,现在差值是 0。绿色是当前还没收走的这一段。
- 24差值回到 0 了,说明从上一段结尾到第 9 位这一段里,L 和 R 一样多,是个完整的平衡段。收下这一段,段数变成 4 段,这段(变蓝)收走,下一段从第 10 位重新开始数。
- 2510 个字符全扫完,差值正好停在 0,整串被切成 4 段:开头两段各是一个 "LR",中间攒出一个 "LLRR",最后又一个 "LR"。每段 L 和 R 都一样多,段数最多就是 4,答案站得住。
⚠️ 容易写错的地方
✗ 错：以为要枚举所有切法或用回溯、动态规划,担心贪心不是最优
✓ 对：直接贪心:从左扫,差值一归零就切,这样切出的段数最多
每个让差值归零的位置都是合法切点,能早切就早切,剩下的部分仍然平衡,不浪费任何一个可切位置,段数自然最多
✗ 错：另开两个计数器分别数 L 和 R,再时时比较,写得很绕
✓ 对：一个计数器记差值就够,遇 L 加一遇 R 减一
我们只关心 L 和 R 是否相等,也就是差值是否为 0,一个计数器记差值最直接,省一半变量
✗ 错：看到差值变成负数就慌,以为算错了
✓ 对：只判断差值等不等于 0,正负都无所谓
如果串从 R 开头,差值会先变负;但只要某一刻回到 0,就说明这一段 L 和 R 相等,可以切,中间的正负号不影响结论
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from 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 ansC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
int balancedStringSplit(string s) {
int ans = 0, l = 0;
for (char c : s) {
if (c == 'L')
++l;
else
--l;
if (l == 0) ++ans;
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int balancedStringSplit(String s) {
int ans = 0, l = 0;
for (char c : s.toCharArray()) {
if (c == 'L') {
++l;
} else {
--l;
}
if (l == 0) {
++ans;
}
}
return ans;
}
}复杂度
时间
O(n)
n 为字符串长度。从左到右每个字符只看一遍,做一次加减和一次「是否归零」判断,整体是线性扫描
空间
O(1)
自始至终只用了差值计数器和段数计数器两个整数,没有额外的数组或栈,峰值占用是常数
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 分割平衡字符串 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么贪心每次差值归零就切,一定能得到最多的段数?+
因为只要某个前缀平衡,它就是一个合法的切点。贪心做法是一遇到平衡就立刻切,相当于把整串拆成一连串「最短的平衡块」。如果在某个平衡位置故意不切、留到后面再切,只会把两个小平衡块并成一个大段,段数只会变少不会变多。所以能切就切,得到的段数最大。
计数器记「L 的个数减 R」和记「R 减 L」有区别吗?+
没有本质区别。两种记法只是中间的正负号相反,我们关心的只是它什么时候等于 0。无论哪种记法,归零的时刻完全一样,切点也一样,最终段数相同。
这题的时间和空间复杂度是多少?+
时间 O(n),n 是字符串长度,每个字符只扫一遍,做一次加减和一次判断。空间 O(1),全程只用差值计数器和段数计数器两个整数,不开额外的数组或栈。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 分割平衡字符串 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。