1221. Split a String in Balanced Strings

Reformulated question¶

Split a balanced string of only 'L' and 'R' into the most balanced pieces possible, where each piece has the same number of 'L' and 'R'.

• Example:
  • Input: s = "RLRRLLRLRL"
  • Split: "RL" | "RRLL" | "RL" | "RL"
  • Output: 4

Key trick¶

Scan once with a balance counter:

• +1 for 'R'
• -1 for 'L'
• Every time balance becomes 0, you can cut there.

Greedy is optimal because cutting at the earliest valid point leaves the most room for more balanced parts later.

Trap¶

Common mistakes:

• Recounting characters for every substring, which is unnecessary.
• Building actual substrings instead of just counting cuts.
• Overthinking with stacks or two pointers.
• Forgetting that the input string is already globally balanced.

Why is this question interesting?¶

It is a clean greedy problem:

• The local choice is obviously safe.
• A single integer state solves it.
• It tests whether you see structure instead of simulating substrings.

Solve the problem with idiomatic python¶

class Solution:
    def balancedStringSplit(self, s: str) -> int:
        # balance > 0 means more R seen, balance < 0 means more L seen
        balance = 0
        parts = 0

        for ch in s:
            if ch == "R":
                balance += 1
            else:
                balance -= 1

            # whenever prefix is balanced, greedily cut here
            if balance == 0:
                parts += 1

        return parts

There is no standard library function that solves this exact problem more directly or better.

Pytest test¶

import pytest

@pytest.mark.parametrize(
    ("s", "expected"),
    [
        ("RLRRLLRLRL", 4),
        ("RLRRRLLRLL", 2),
        ("LLLLRRRR", 1),
        ("RL", 1),
        ("LR", 1),
        ("RLLR", 2),
        ("RRLL", 1),
        ("LRLRLR", 3),
        ("LLRRLRRL", 2),
    ],
)
def test_balanced_string_split(s, expected):
    assert Solution().balancedStringSplit(s) == expected

Comment my solution¶

Your solution is correct on many cases, but it is not a good interview solution.

Issues:

• It uses Counter repeatedly, making it much slower than needed.
• It builds substrings, but no substring materialization is needed.
• It scans from right to left in steps of 2, which is hard to justify and makes the idea unclear.
• s[i - 1] at i == 0 uses Python negative indexing by accident.
• return len(ans) or 1 is a patchy fallback, not part of the core logic.

A better interview answer is:

• One pass
• One counter
• Count whenever balance returns to zero

from collections import Counter

class Solution:
    def balancedStringSplit(self, s: str) -> int:
        def is_balanced(x):
            return Counter(x)['L'] == Counter(x)['R']

        ans = []
        ss = ''
        for i in range(len(s) - 1,-1,-2):
            ss += s[i] + s[i - 1]
            if is_balanced(ss):
                ans.append(ss)
                ss = ''
        return len(ans) or 1