Question

1221. Split a String in Balanced Strings

中文文档

Description

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.

Solutions

Solution 1: Greedy

We use a variable $l$ to maintain the current balance of the string, i.e., the value of $l$ is the number of 'L's minus the number of 'R's in the current string. When the value of $l$ is 0, we have found a balanced string.

We traverse the string $s$. When we traverse to the $i$-th character, if $s[i] = L$, then the value of $l$ is increased by 1, otherwise, the value of $l$ is decreased by 1. When the value of $l$ is 0, we increase the answer by 1.

The time complexity is $O(n)$, and the space complexity is $O(1)$. Here, $n$ is the length of the string $s$.

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

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

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

func balancedStringSplit(s string) int {
  ans, l := 0, 0
  for _, c := range s {
    if c == 'L' {
      l++
    } else {
      l--
    }
    if l == 0 {
      ans++
    }
  }
  return ans
}

/**
 * @param {string} s
 * @return {number}
 */
var balancedStringSplit = function (s) {
  let ans = 0;
  let l = 0;
  for (let c of s) {
    if (c == 'L') {
      ++l;
    } else {
      --l;
    }
    if (l == 0) {
      ++ans;
    }
  }
  return ans;
};