分割平衡字符串 图解题解

怎样算平衡串，最多能切几段

先把「平衡」说清楚：一个由 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)。

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 ans

C++

#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;
    }
}