LeetCode（String)1221. Split a String in Balanced Strings

青旅半醒 2023-09-23 21:56 66阅读 0赞

# 1.问题 #

Balanced strings are those that have an equal quantity of ‘L’ and ‘R’ characters.

Given a balanced string s, split it into some number of substrings such that:

Each substring is balanced.  
Return the maximum number of balanced strings you can obtain.  
Example 1:

> Input: s = “RLRRLLRLRL”  
> Output: 4  
> Explanation: s can be split into “RL”, “RRLL”, “RL”, “RL”, each substring contains same number of ‘L’ and ‘R’.

Example 2:

> Input: s = “RLRRRLLRLL”  
> Output: 2  
> Explanation: s can be split into “RL”, “RRRLLRLL”, each substring contains same number of ‘L’ and ‘R’.  
> Note that s cannot be split into “RL”, “RR”, “RL”, “LR”, “LL”, because the 2nd and 5th substrings are not balanced.

Example 3:

> Input: s = “LLLLRRRR”  
> Output: 1  
> Explanation: s can be split into “LLLLRRRR”.

Constraints:

2 <= s.length <= 1000  
s\[i\] is either ‘L’ or ‘R’.  
s is a balanced string.

# 2.解题思路 #

## 方法1： ##

> 解决这个问题的方法是循环遍历字符串，并在遇到时不断增加 L 和 R 的计数。  
> 1.定义L 和 R 的计数的变量，以及返回字符串个数的变量sum  
> 2.s转为char\[\] 方便遍历数组  
> 3.如果字符等于”R“，R的计数加1，否则L的计数加1  
> 4.R的计数=L的计数,返回字符串个数的变量sum加1  
> 5.返回sum

## 方法2： ##

> 1.定义result，sum初始值为0  
> 2.for循环遍历，如果s的元素为L，sum为1；如果为R，为-1  
> 3.sum中R和L的个数和为0，result加一  
> 4.返回值result

# 3.代码 #

## 代码1： ##

class Solution {
        
        public int balancedStringSplit(String s) {
        
            int countR = 0;//1.定义L 和 R 的计数的变量，以及返回字符串个数的变量sum
            int countL =0;
            int sum=0;
            char[] d = s.toCharArray();//2.s转为char[] 方便遍历数组
            for(int i =0;i<d.length;i++){
        
                if(d[i]=='R'){
        //3.如果字符等于”R“，R的计数加1，否则L的计数加1
                    countR++;
                }else{
        
                    countL++;
                }
                if(countR == countL){
        //4.R的计数=L的计数,返回字符串个数的变量sum加1，
                    sum++;
                }
            }
            return sum;//5.返回sum
        }
    }

## 代码2： ##

class Solution {
        
        public int balancedStringSplit(String s) {
        
            int result = 0, sum = 0;//1.定义result，sum初始值为0
            for (int i = 0; i < s.length(); i++) {
        //2.for循环遍历，如果s的元素为L，sum为1；如果为R，为-1
                sum += s.charAt(i) == 'L' ? 1 : -1;
                if (sum == 0) result++;//3.sum中R和L的个数和为0，result加一
            }
            return result;//4.返回值result
        }
    }

> 以下代码和代码2的解题思路相同

class Solution {
        
        public int balancedStringSplit(String s) {
        
            int result = 0;
            int sum = 0;
            
            for (char letter : s.toCharArray()) {
        
                sum += (letter == 'R' ? 1 : -1);
                if (sum == 0) {
        
                    result++;
                }
            }
            
            return result;
        }
    }