力扣1221：一次扫描解决分割平衡字符串 时间O(n)空间O(1)

题目重解

给定一个仅包含'L'和'R'的字符串，要求将其分割成尽可能多的子串，且每个子串中'L'和'R'的数量相等。例如输入"RLRRLLRLRL"，可以分割为"RL"、"RRLL"、"RL"、"RL"四个平衡子串。

解题思路

这段代码采用了贪心算法和双计数器策略：

1.使用Lsum和Rsum分别统计当前遍历过程中'L'和'R'的数量

2.每当两个计数器相等时，说明找到一个平衡子串

3.计数器归零后继续寻找下一个平衡子串

4.最终返回找到的平衡子串总数

时间复杂度为O(n)，空间复杂度为O(1)，解决此类问题的最优方案。

代码解析

class Solution {
public:
    int balancedStringSplit(string s) {
        int Lsum = 0, Rsum = 0; // 'L'和'R'的计数器
        int cnt = 0; // 平衡子串计数器
        
        for (int i = 0; i < s.size(); i++) {
            s[i] == 'L' ? Lsum++ : Rsum++; // 根据字符类型增加对应计数器
            
            if (Lsum == Rsum) // 发现平衡子串
                cnt++; // 平衡子串数+1
        }
        return cnt; // 返回总平衡子串数
    }
};