Split a String in Balanced Strings: Greedy Balance Counter
A balanced string has an equal number of 'L' and 'R' characters. Given a balanced string s, split it into the maximum number of balanced substrings and return the count.
This is LeetCode 1221: Split a String in Balanced Strings, and it is one of the cleanest examples of the greedy balance counter pattern. The technique you learn here applies to any problem where you need to find balanced segments in a sequence of two types.
Why this problem matters
Many problems ask you to work with strings containing two types of characters (parentheses, binary digits, L/R labels) and find balanced or valid segments. The core idea is always the same: track a running counter and react when it reaches a target value. In this problem the target is zero, and the reaction is "split here."
Once you internalize this pattern, you will recognize it in parentheses validation, balanced partition problems, and any scenario where two opposing forces need to cancel out.
The key insight
Scan left to right and keep a balance counter. Add +1 for every 'R' and -1 for every 'L' (or the other way around, it does not matter). Every time the balance hits 0, you have found a balanced substring. Split greedily at that point, because waiting longer can never produce more splits. If a balanced string contains a balanced prefix, removing that prefix leaves another balanced string, so splitting early is always optimal.
The solution
def balanced_string_split(s: str) -> int:
balance = 0
count = 0
for ch in s:
if ch == "R":
balance += 1
else:
balance -= 1
if balance == 0:
count += 1
return count
The algorithm walks through the string once. For each character, it adjusts the balance counter. When the counter returns to zero, it means the number of R's and L's seen since the last split (or since the start) are equal. That is exactly when you record a split and let the counter start fresh for the next segment.
Greedy splitting works here because you are guaranteed the input is balanced overall. Every time balance reaches zero, the remaining suffix is also balanced, so you never "waste" characters by splitting too early.
Visual walkthrough
Let's trace through the example s = "RLRRLLRLRL" step by step. Watch the balance counter and notice how every time it hits zero, a new split is recorded.
Step 1: Start scanning. i=0 is R, balance goes to +1.
balance = +1 (not zero yet, keep going). Count = 0.
Step 2: i=1 is L, balance drops to 0. Split here.
balance = 0, so we found a balanced substring 'RL'. Count = 1.
Step 3: Scan i=2 through i=5. Balance goes +1, +2, +1, then 0.
balance hits 0 at i=5, so 'RRLL' is balanced. Count = 2.
Step 4: Scan i=6 and i=7. Balance goes +1, then 0.
balance hits 0 at i=7, so 'RL' is balanced. Count = 3.
Step 5: Scan i=8 and i=9. Balance goes +1, then 0. Done.
balance hits 0 at i=9, so 'RL' is balanced. Count = 4. Return 4.
Notice that the balance never stays at zero for long. Each time it returns to zero, we lock in a balanced substring and move on. The four substrings are "RL", "RRLL", "RL", and "RL".
Complexity analysis
| Approach | Time | Space |
|---|---|---|
| Greedy balance counter | O(n) | O(1) |
Time is O(n) where n is the length of the string. You visit each character exactly once and do constant work per character.
Space is O(1). You only need two integer variables: the balance counter and the split count. No extra data structures are required.
The building blocks
1. Balance tracking
balance = 0
for ch in s:
if ch == "R":
balance += 1
else:
balance -= 1
This is the fundamental pattern: assign +1 to one character type and -1 to the other, then accumulate. The running total tells you how "unbalanced" the current window is. You will use this same counter in valid parentheses checking, where ( is +1 and ) is -1.
2. Greedy split on zero balance
if balance == 0:
count += 1
Every time the counter hits zero, you know the substring from the last split point to the current index is perfectly balanced. By splitting immediately, you maximize the number of balanced pieces. This greedy choice works because balanced substrings are self-contained: splitting one out cannot break the balance of the rest.
Edge cases
- Minimum input "RL" or "LR": the balance hits zero after two characters. Return
1. - Already maximally split: a string like "RLRLRL" splits into three pieces. Every pair is balanced.
- Deeply nested: a string like "RRRRLLLL" has balance going to
+4before returning to zero. Only one split at the very end. - Alternating nesting: "RLLR" has balance going
+1, 0, -1, 0. That gives two splits: "RL" and "LR". - All R's first then all L's: "RRLL" returns
1. The balance only hits zero once.
From understanding to recall
The greedy balance counter is simple to understand. You track a running total, and you split when it hits zero. But in an interview, you also need to explain why greedy works here, and that explanation needs to flow naturally. "The input is guaranteed balanced, so every time balance reaches zero the remaining suffix is also balanced" is the key sentence.
Spaced repetition helps you internalize both the code and the reasoning. You practice writing the loop, the counter logic, and the split condition from memory until they are automatic. After a few sessions, you see "split balanced string" in a problem and the entire solution appears without hesitation.
Related posts
- Valid Parentheses - Another problem using a balance counter to track paired characters
- Generate Parentheses - Building balanced strings with a counter constraint
- Longest Valid Parentheses - Finding balanced substrings using a counter
CodeBricks breaks Split a String in Balanced Strings into its balance tracking and greedy splitting building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a greedy problem shows up in your interview, you do not think about it. You just write it.