Split a String in Balanced Strings

Difficulty: Easy | Acceptance: 87.40% | Paid: No Topics: String, Greedy, Counting

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

Given a balanced string s, split it in the maximum amount of balanced strings.

Return the maximum amount of split balanced strings.

• Examples
• Constraints
• Approach 1: Greedy Counting
• Approach 2: Stack Simulation
• Approach 3: Brute Force

Examples

Input: s = "RLRRLLRLRL"
Output: 4
Explanation: s can be split into "RL", "RRLL", "RL", "RL", each substring is balanced.

Input: s = "RLLLLRRRLR"
Output: 3
Explanation: s can be split into "RL", "LLLRRR", "LR", each substring is balanced.

Input: s = "LLLLRRRR"
Output: 1
Explanation: s can be split into "LLLLRRRR".

Constraints

1 <= s.length <= 1000
s[i] is either 'L' or 'R'
s is a balanced string.

Approach 1: Greedy Counting

Intuition Since the total string is balanced, we can greedily count characters. Whenever the running count of ‘L’ and ‘R’ becomes equal (count = 0), we have found a valid balanced substring.

Steps

• Initialize count and result to 0.
• Iterate through the string character by character.
• If the character is ‘R’, increment count. If it is ‘L’, decrement count.
• If count becomes 0, increment result as we have found a split point.

class Solution:
    def balancedStringSplit(self, s: str) -> int:
        count = 0
        res = 0
        for c in s:
            if c == 'R':
                count += 1
            else:
                count -= 1
            if count == 0:
                res += 1
        return res

Complexity

• Time: O(n), where n is the length of the string. We traverse the string once.
• Space: O(1), we only use a few integer variables.
• Notes: This is the most optimal solution for this problem.

Approach 2: Stack Simulation

Intuition We can simulate the matching process using a stack. Push ‘R’ onto the stack and pop for ‘L’ (or vice versa). When the stack becomes empty, it means we have found a balanced segment.

Steps

• Initialize an empty stack and result to 0.
• Iterate through the string.
• If the stack is empty or the top of the stack matches the current character, push the character onto the stack.
• Otherwise, pop the top of the stack.
• If the stack is empty after processing the current character, increment result.

class Solution:
    def balancedStringSplit(self, s: str) -> int:
        stack = []
        res = 0
        for c in s:
            if not stack or stack[-1] == c:
                stack.append(c)
            else:
                stack.pop()
            if not stack:
                res += 1
        return res

Complexity

• Time: O(n), we iterate through the string once.
• Space: O(n), in the worst case (e.g., “RRRR”), the stack grows to size n.
• Notes: While conceptually valid for matching problems, it uses extra space compared to the counting approach.

Approach 3: Brute Force

Intuition Iterate through the string, checking every possible prefix to see if it is balanced. If it is, cut it and restart the check from the next character.

Steps

• Initialize result to 0 and start index to 0.
• Iterate i from start to the end of the string.
• Check if the substring s[start...i] is balanced by counting ‘L’ and ‘R’.
• If balanced, increment result, set start to i + 1, and break the inner loop to continue searching.
• Return result.

class Solution:
    def balancedStringSplit(self, s: str) -> int:
        res = 0
        n = len(s)
        i = 0
        while i < n:
            count = 0
            for j in range(i, n):
                if s[j] == 'R':
                    count += 1
                else:
                    count -= 1
                if count == 0:
                    res += 1
                    i = j + 1
                    break
        return res

Complexity

• Time: O(n²), in the worst case we might scan the string multiple times.
• Space: O(1), only a few variables are used.
• Notes: This approach is less efficient than the greedy approach but demonstrates the brute force logic.