“This is the 20th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

The original link

1221. Split Balance String – LeetCode (leetcode-cn.com)

Topic describes

In a balanced string, the number of ‘L’ and ‘R’ characters is the same.

You are given a balanced string s and please split it into as many balanced strings as possible.

Note: Each split string must be a balanced string, and the split balanced string is a continuous substring of the original balanced string.

Returns the maximum number of balanced strings that can be split.

The test case

Example 1:

Input: s = "RLRRLLRLRL" Output: 4 Explanation: S can be split into "RL", "RRLL", "RL", "RL", "RL", each substring contains the same number of 'L' and 'R'.Copy the code

Example 2:

Input: s = "RLLLLRRRLR" Output: 3 Explanation: S can be split into "RL", "LLLRRR", "LR", each substring contains the same number of 'L' and 'R'.Copy the code

Parameter limits

  • 1 <= s.length <= 1000
  • S [I] = 'L' or 'R'
  • sIs abalancestring

Analysis of the

If a string contains an equal number of L and R characters, we need to cut as many subcharacters as possible, and ensure that the number of L and R in the substring is equal

The simplest idea is to iterate over the string from the beginning, counting the number of L and R characters, and when they are equal, clearing the character count and making their subcharacter count +1

We need two character counters, countL and countR, to count and empty separately. This is a bit tedious. We can optimize to a total count: count++ when the character is L; For R, count–; When the count is 0, the substring counts +1

code

var balancedStringSplit = function(s) {
    let count = 0,
        sum = 0;
    s.split(' ').forEach(n= > {
        count = count+(n=='L'?1: -1);
        if(count==0){ sum++; }})return sum;
};
Copy the code

Complexity analysis

  • Time complexity: O(n), where n is the length of string S. We only have to go through s once.

  • Space complexity: O(1). You just need constant space for a few variables.

Today’s force buckle brush problem share here, thank you for reading ~