Algorithm

Problem Name: 1221. Split a String in Balanced Strings

Problem Link: https://leetcode.com/problems/split-a-string-in-balanced-strings/
 

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.

Code Examples

#1 Code Example with Java Programming

Code - Java Programming


class Solution {
    public int balancedStringSplit(String s) {
        int count = 0;
        int val = 0;
        for (char c : s.toCharArray()) {
            val += c == 'L' ? -1 : 1;
            if (val == 0) {
                count++;
            }
        }
        return count;
    }
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
s = "RLRRLLRLRL"

Output

x
–
+
cmd
4

#2 Code Example with Javascript Programming

Code - Javascript Programming


const balancedStringSplit = function(s) {
  let res = 0, num = 0
  for(let ch of s) {
    num += ch === 'L' ? 1 : -1
    if(num === 0) res++
  }
  return res
};
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
s = "RLRRLLRLRL"

Output

x
–
+
cmd
4

#3 Code Example with Python Programming

Code - Python Programming


class Solution:
    def balancedStringSplit(self, s: str) -> int:
        res = cnt = 0         
        for c in s:
            cnt += c == 'L'
            cnt -= c == 'R'
            res += cnt == 0
        return res
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
s = "RLRRRLLRLL"

Output

x
–
+
cmd
2

#4 Code Example with C# Programming

Code - C# Programming


namespace LeetCode
{
    public class _1221_SplitAStringInBalancedStrings
    {
        public int BalancedStringSplit(string s)
        {
            var count = 0;
            var result = 0;
            foreach (var ch in s)
            {
                count += ch == 'L' ? 1 : -1;
                if (count == 0)
                    result++;
            }

            return result;
        }
    }
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
s = "RLRRRLLRLL"

Output

x
–
+
cmd
2
Advertisements

Demonstration

Previous
#1220 Leetcode Count Vowels Permutation Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#1222 Leetcode Queens That Can Attack the King Solution in C, C++, Java, JavaScript, Python, C# Leetcode