{x}
blog image

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.

Solution Explanation:

The problem asks to find the maximum number of balanced substrings within a given balanced string. A balanced string is defined as a string containing an equal number of 'L' and 'R' characters. The solution leverages a greedy approach for efficiency.

Approach:

The core idea is to track the running balance of 'L' and 'R' characters. We initialize a counter l to 0. We iterate through the input string s.

  • If we encounter an 'L', we increment l (increasing the balance of 'L's).
  • If we encounter an 'R', we decrement l (decreasing the balance of 'L's).

Whenever the balance l becomes 0, it means we've found a balanced substring. We increment our answer counter ans. This works because the problem guarantees the input string is already balanced, so any time the balance hits zero, it represents a complete balanced substring.

Time and Space Complexity Analysis:

  • Time Complexity: O(n), where n is the length of the input string. We iterate through the string once.
  • Space Complexity: O(1). We only use a constant amount of extra space to store the counter l and the answer ans.

Code Implementation (Python, Java, C++, Go, JavaScript):

The provided code snippets in different languages all implement this greedy approach. They are highly similar, differing only in syntax specific to each language. The core logic remains the same: iterating through the string, updating the balance l, and incrementing the answer when a balanced substring is detected (l == 0).

For example, the Python code is particularly concise:

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

All other languages (Java, C++, Go, JavaScript) follow a similar structure, maintaining a running balance and counting the number of times the balance returns to zero. They all achieve a linear time complexity and constant space complexity due to the efficient greedy approach.