Split a String in Balanced Strings (LeetCode 1221): Greedy With a Running Balance

The problem

A string of L and R characters is balanced when it has the same number of each. Given a balanced string, split it into the maximum number of balanced substrings. For "RLRRLLRLRL" the answer is 4: RL, RRLL, RL, RL.

The greedy idea

Walk the string and keep a counter: +1 for R, -1 for L. Every time the counter returns to 0, the prefix since the last cut is balanced, so cut there and count it.

def balanced_split(s):
    balance = 0
    pieces = 0
    for ch in s:
        balance += 1 if ch == "R" else -1
        if balance == 0:
            pieces += 1
    return pieces

O(n) time and O(1) extra space.

Why cutting early is never wrong

Suppose an optimal split does not cut at the first point where the balance hits zero. Its first piece then contains that balanced prefix plus a remainder, and the remainder must also be balanced (its count difference is the piece's difference minus the prefix's, which is 0 minus 0). So you can split that first piece into two, which gives at least as many pieces. Repeating the argument shows the greedy cuts are optimal.

Follow-ups interviewers ask

Explaining it out loud

The part people stumble on is the exchange argument. Practise saying "any longer first piece can be split at the first zero without losing pieces" in one sentence before moving to code.

Disclosure: I work on Linkjob AI. If you want practice explaining solutions like this under time pressure, we build AI help for online coding assessments.