Problem Description

Given a string s consisting only of the characters 'L' and 'R', you are asked to split the string into the maximum number of non-overlapping substrings such that each substring is "balanced". A balanced string is defined as one where the number of 'L' characters is equal to the number of 'R' characters.

You must return the maximum number of balanced substrings you can obtain. Each character from s must be used exactly once, and substrings must be contiguous. You cannot reuse elements across substrings.

Example:
Input: s = "RLRRLLRLRL"
Output: 4
Explanation: The string can be split into "RL", "RRLL", "RL", "RL", each of which is balanced.

Constraints:

• 1 ≤ s.length ≤ 1000
• s[i] is either 'L' or 'R'

Thought Process

The first instinct might be to try all possible ways to split the string and check if the resulting substrings are balanced. However, this brute-force approach would be inefficient, especially as the length of s grows.

Instead, it's helpful to look for a more efficient way. Since a balanced substring requires an equal number of 'L' and 'R', we can track the "balance" as we iterate through the string. If we use a counter that increases for one character (say, 'L') and decreases for the other ('R'), we can identify points where the counter returns to zero — these are the endpoints of balanced substrings.

This realization leads to a greedy approach: as soon as we find a balanced substring, we split there and continue. This ensures we get the maximum number of balanced substrings.

Solution Approach

To solve this problem efficiently, we use a simple counter to track the balance between 'L' and 'R' as we traverse the string. Here is the step-by-step approach:

1. Initialize a balance variable to 0. This will track the difference between the number of 'L' and 'R' characters seen so far.
2. Initialize a count variable to 0. This will keep track of the number of balanced substrings found.
3. Iterate through each character in the string s:
   • If the character is 'L', increment balance by 1.
   • If the character is 'R', decrement balance by 1.
   • Whenever balance becomes 0, it means we have found a balanced substring. Increment count by 1.
4. After processing the entire string, return count as the answer.

This approach is greedy, as it makes a split as soon as a balanced substring is found, which ensures the maximum number of splits.

Example Walkthrough

Let's walk through the example input s = "RLRRLLRLRL" step by step:

• Start with balance = 0, count = 0.
• Index 0: 'R' → balance = -1
• Index 1: 'L' → balance = 0 (Found balanced substring! count = 1)
• Index 2: 'R' → balance = -1
• Index 3: 'R' → balance = -2
• Index 4: 'L' → balance = -1
• Index 5: 'L' → balance = 0 (Found balanced substring! count = 2)
• Index 6: 'R' → balance = -1
• Index 7: 'L' → balance = 0 (Found balanced substring! count = 3)
• Index 8: 'R' → balance = -1
• Index 9: 'L' → balance = 0 (Found balanced substring! count = 4)

At the end, we have count = 4, which matches the expected output.

Time and Space Complexity

Brute-force approach:
Trying all possible splits and checking if each substring is balanced would require examining all possible partitions. There are exponentially many ways to split a string, so the time complexity would be much greater than O(n), potentially O(2ⁿ).

Optimized (greedy) approach:
We only need a single pass through the string, updating two variables at each step. So, the time complexity is O(n), where n is the length of the string.
The space complexity is O(1) since we use only a few integer variables, regardless of input size.

Summary

The key insight to solving this problem efficiently is to use a running balance counter. By incrementing or decrementing the balance as we encounter 'L' or 'R', we can identify balanced substrings in a single pass. This greedy approach is optimal and elegant, allowing us to maximize the number of balanced splits with minimal computation.

This technique — reducing a problem to a prefix sum or running balance — is a powerful tool in many string and array problems, especially where "balance" or "matching" constraints are involved.

Code Implementation

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

class Solution {
public:
    int balancedStringSplit(string s) {
        int balance = 0, count = 0;
        for (char c : s) {
            if (c == 'L') balance++;
            else balance--;
            if (balance == 0) count++;
        }
        return count;
    }
};
      

class Solution {
    public int balancedStringSplit(String s) {
        int balance = 0, count = 0;
        for (char c : s.toCharArray()) {
            if (c == 'L') balance++;
            else balance--;
            if (balance == 0) count++;
        }
        return count;
    }
}
      

var balancedStringSplit = function(s) {
    let balance = 0, count = 0;
    for (let c of s) {
        if (c === 'L') balance++;
        else balance--;
        if (balance === 0) count++;
    }
    return count;
};