LeetCode Problem 1221

Difficulty: 🟢 Easy
Topics: String, Greedy, Counting

Solution

LeetCode 1221 - Split a String in Balanced Strings

Problem Understanding

This problem gives us a string s that contains only the characters 'L' and 'R'. The string is guaranteed to already be balanced overall, meaning the total number of 'L' characters equals the total number of 'R' characters.

Our task is to split this string into the maximum possible number of non-empty substrings such that every substring is also balanced. A substring is considered balanced when it contains the same number of 'L' and 'R' characters.

The important detail is that we are not simply checking whether the entire string is balanced. We must determine how many balanced pieces we can divide it into while maximizing the count of those pieces.

For example, in the string "RLRRLLRLRL":

• "RL" is balanced
• "RRLL" is balanced
• "RL" is balanced
• "RL" is balanced

This gives a total of 4 balanced substrings, which is the maximum possible.

The input size is small, since s.length <= 1000. This means even less efficient solutions could technically work, but the structure of the problem allows for a very clean greedy solution with linear time complexity.

A few important observations come directly from the constraints:

• The string contains only two possible characters.
• The entire string is guaranteed to be balanced.
• Every valid split must preserve character order.
• We want the maximum number of balanced substrings, so smaller valid balanced pieces are generally better.

Several edge cases are worth considering early:

• A string like "LR" or "RL" is already the smallest possible balanced substring.
• A string like "LLLLRRRR" is balanced overall, but cannot be split into smaller balanced pieces.
• Alternating strings such as "RLRLRL" produce many balanced substrings.
• Since the input is guaranteed balanced, we never need to handle invalid final states where counts do not match.

Approaches

Brute Force Approach

A brute force solution would try every possible way to split the string into substrings. For each partitioning, we would verify whether every substring contains an equal number of 'L' and 'R'.

This approach is correct because it explores all possible split combinations and selects the partitioning with the largest number of balanced pieces.

However, this strategy is extremely inefficient. A string of length n has exponentially many possible ways to partition it. For every partition, we would also need to count characters inside each substring.

Although the constraint is only 1000 characters, exponential partition generation is still far too slow.

Optimal Greedy Approach

The key insight is that whenever we encounter a prefix where the number of 'L' and 'R' characters becomes equal, we should immediately split there.

Why is this greedy choice optimal?

A balanced prefix can safely become its own substring because it already satisfies the requirement. Delaying the split would only merge it with later characters, reducing the total number of substrings we can form.

Therefore, the best strategy is:

• Traverse the string once.
• Maintain a running balance.
• Increment the balance for one character type and decrement for the other.
• Whenever the balance becomes zero, we have found one balanced substring.

This works because a zero balance means we have seen equal numbers of 'L' and 'R'.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n * n)	O(n)	Tries every possible partition and validates each substring
Optimal Greedy	O(n)	O(1)	Single pass using a running balance counter

Algorithm Walkthrough

1. Initialize two variables:

• balance = 0
• balanced_count = 0

The balance variable tracks the difference between the number of 'R' and 'L' characters seen so far. 2. Traverse the string character by character. 3. For each character:

• If the character is 'R', increment balance.
• If the character is 'L', decrement balance.

We could reverse these operations and the algorithm would still work. What matters is consistency. 4. After updating the balance, check whether balance == 0.

A balance of zero means the current segment contains equal numbers of 'L' and 'R'. 5. Whenever the balance becomes zero:

• Increment balanced_count.
• Conceptually start a new substring from the next character.

6. Continue until the end of the string.
7. Return balanced_count.

Why it works

The algorithm maintains the invariant that balance represents the difference between the counts of 'R' and 'L' in the current substring being formed.

Whenever the balance reaches zero, the current substring is guaranteed to be balanced. Splitting immediately is always optimal because using the smallest possible valid balanced substring leaves more characters available to form additional balanced substrings later.

Therefore, greedily splitting at every zero balance maximizes the number of balanced substrings.

Python Solution

class Solution:
    def balancedStringSplit(self, s: str) -> int:
        balance = 0
        balanced_count = 0

        for char in s:
            if char == 'R':
                balance += 1
            else:
                balance -= 1

            if balance == 0:
                balanced_count += 1

        return balanced_count

The implementation directly follows the greedy algorithm.

The variable balance tracks the running difference between 'R' and 'L'. Each 'R' increases the balance, while each 'L' decreases it.

As we scan the string from left to right, every time the balance becomes zero, we know we have completed one balanced substring. At that point, we increment balanced_count.

The algorithm never needs to explicitly store substrings because only the count matters. This keeps the memory usage constant.

Go Solution

func balancedStringSplit(s string) int {
    balance := 0
    balancedCount := 0

    for _, char := range s {
        if char == 'R' {
            balance++
        } else {
            balance--
        }

        if balance == 0 {
            balancedCount++
        }
    }

    return balancedCount
}

The Go implementation is nearly identical to the Python version.

Go iterates through the string using a range loop, which returns Unicode rune values. Since the input contains only ASCII characters 'L' and 'R', rune handling is straightforward.

No additional slices or arrays are required, so the solution maintains constant extra space usage.

Worked Examples

Example 1

Input:

s = "RLRRLLRLRL"

Step-by-step Trace

Index	Character	Balance	Balanced Count	Explanation
0	R	1	0	One more R than L
1	L	0	1	First balanced substring: "RL"
2	R	1	1	Start next substring
3	R	2	1	More R characters
4	L	1	1	Difference reduced
5	L	0	2	Second balanced substring: "RRLL"
6	R	1	2	Start next substring
7	L	0	3	Third balanced substring: "RL"
8	R	1	3	Start next substring
9	L	0	4	Fourth balanced substring: "RL"

Final answer:

4

Example 2

Input:

s = "RLRRRLLRLL"

Step-by-step Trace

Index	Character	Balance	Balanced Count	Explanation
0	R	1	0	More R characters
1	L	0	1	First balanced substring: "RL"
2	R	1	1	Start next substring
3	R	2	1	More R characters
4	R	3	1	More R characters
5	L	2	1	Difference reduced
6	L	1	1	Difference reduced
7	R	2	1	More R characters
8	L	1	1	Difference reduced
9	L	0	2	Second balanced substring

Final answer:

2

Example 3

Input:

s = "LLLLRRRR"

Step-by-step Trace

Index	Character	Balance	Balanced Count	Explanation
0	L	-1	0	More L characters
1	L	-2	0	More L characters
2	L	-3	0	More L characters
3	L	-4	0	More L characters
4	R	-3	0	Difference reduced
5	R	-2	0	Difference reduced
6	R	-1	0	Difference reduced
7	R	0	1	Entire string balanced

Final answer:

1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is processed exactly once
Space	O(1)	Only a few integer variables are used

The algorithm performs a single linear scan through the string. Every operation inside the loop takes constant time, so the total runtime is proportional to the string length.

The space complexity is constant because the algorithm stores only two integer counters regardless of input size.

Test Cases

solution = Solution()

assert solution.balancedStringSplit("RLRRLLRLRL") == 4  # provided example
assert solution.balancedStringSplit("RLRRRLLRLL") == 2  # provided example
assert solution.balancedStringSplit("LLLLRRRR") == 1  # provided example

assert solution.balancedStringSplit("RL") == 1  # smallest balanced string
assert solution.balancedStringSplit("LR") == 1  # reversed smallest balanced string

assert solution.balancedStringSplit("RLRL") == 2  # multiple tiny balanced substrings
assert solution.balancedStringSplit("LRLR") == 2  # alternating pattern

assert solution.balancedStringSplit("RRLL") == 1  # single larger balanced substring
assert solution.balancedStringSplit("RLLR") == 2  # splits into "RL" and "LR"

assert solution.balancedStringSplit("RLRLRLRL") == 4  # maximum frequent splitting
assert solution.balancedStringSplit("LLRRLR") == 2  # mixed grouping pattern

assert solution.balancedStringSplit("RRRLLL") == 1  # only balanced as whole
assert solution.balancedStringSplit("LRRLLR") == 2  # multiple balanced sections

Test Summary

Test	Why
"RLRRLLRLRL"	Validates standard example with multiple splits
"RLRRRLLRLL"	Verifies uneven intermediate balances
"LLLLRRRR"	Confirms whole-string-only balance
"RL"	Tests smallest valid balanced input
"LR"	Tests smallest balanced input in reverse order
"RLRL"	Verifies repeated small balanced substrings
"LRLR"	Confirms alternating pattern behavior
"RRLL"	Tests single large balanced block
"RLLR"	Ensures multiple adjacent balanced groups work
"RLRLRLRL"	Stress test for maximum splitting
"LLRRLR"	Verifies mixed grouping patterns
"RRRLLL"	Tests delayed balance recovery
"LRRLLR"	Confirms balance resets correctly

Edge Cases

One important edge case is the smallest valid input, such as "RL" or "LR". A buggy implementation might incorrectly require longer substrings or mishandle the first balance reset. This implementation correctly identifies the balance reaching zero after processing two characters and returns 1.

Another important case is when the entire string is balanced but cannot be split earlier, such as "LLLLRRRR" or "RRRLLL". Some incorrect greedy implementations may try to split prematurely without checking the actual balance condition. This solution only splits when the balance becomes exactly zero, so it correctly returns 1.

A third important edge case is highly alternating strings like "RLRLRLRL". These inputs create many tiny balanced substrings. An implementation that delays splitting would produce too few substrings. Because this algorithm greedily splits immediately whenever the balance reaches zero, it correctly maximizes the number of balanced substrings.