一起学算法-1221. 分割平衡字符串

一、题目

LeetCode-1221. 分割平衡字符串
地址：https://leetcode-cn.com/problems/split-a-string-in-balanced-strings/

难度：简单
在一个 平衡字符串 中，'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'。

二、解题思路

题目要求子串中ΣL=ΣR，并未要求L和R结构对称。因此，只要遍历过程中ΣL=ΣR就进行分割，分割的次数就是最大。

class Solution {
public:
    int balancedStringSplit(string s) {
        int L = 0,R = 0,res = 0;
        for(int i = 0; i < s.size(); ++i){
            if(s[i] == 'L'){
                L++;
            }else{
                R++;
            }
            if(L == R ){
                res++;
                L = 0;
                R = 0;
            }
        }
        return res;
    }
};

代码似乎还能优化一点点，最终代码如下。

三、最终实现过程

c++

class Solution {
public:
    int balancedStringSplit(string s) {
        int t = 0,res = 0;
        for(int i = 0; i < s.size(); ++i){
            if(s[i] == 'L'){
                t++;
            }else{
                t--;
            }
            if(t == 0 ){
                res++;
            }
        }
        return res;
    }
};

PHP

class Solution {

    /**
     * @param String $s
     * @return Integer
     */
    function balancedStringSplit($s) {
        $res = 0;
        $t = 0;
        for($i = 0; $i < strlen($s);$i++){
            if(substr($s,$i,1) == "L"){
                $t++;
            }else{
                $t--;
            }
            if($t == 0){
                $res++;
            }
        }
        return $res;
    }
}

JavaScript

/**
 * @param {string} s
 * @return {number}
 */
var balancedStringSplit = function(s) {
    let res = 0,t = 0;
    for(let i = 0;i < s.length; i++){
        if(s[i] == "L"){
            t++;
        }else{
            t--;
        }
        if(t == 0){
            res++;
        }
    }
    return res;
};

四、小结

1. 时间复杂度：O(n)，其中n表示字符串长度。只遍历了一次字符串，所以时间复杂度为线性。
2. 空间复杂度：O(1)，只用到了几个变量，没有新建复杂数据结构，所以空间复杂度为常量。

分享不易，如果你觉得还有用就点个赞再走吧！