1049. Cutting the String Into Balanced Pieces

A string contains only L and R, with exactly as many of each. Cut it into consecutive pieces so that every piece also has equal numbers of L and R. Print the LARGEST number of pieces possible.

RLRRLLRLRL -> 4 RL | RRLL | RL | RL RLRRRLLRLL -> 2 RL | RRRLLRLL LLLLRRRR -> 1 no cut is legal before the end LRLRLRLR -> 4

The whole string is always one legal piece, so the answer is at least 1.

## What most people try first

A table: best[i] is the most pieces the first i characters can be cut into, filled by trying every earlier cut j and testing whether s[j..i-1] is balanced. That is O(n^2) splits and each test costs its own length, so O(n^3) naively or O(n^2) with prefix counts. At n = 200000 that is 4 * 10^10.

## Cut the moment you are allowed to

Carry a running balance: +1 for L and -1 for R. A prefix is balanced exactly when its balance is 0, so:

balance = 0, pieces = 0 for each character: balance += (c == 'L') ? +1 : -1 if balance == 0: pieces += 1

The answer is how many times the running balance touches zero.

## Why cutting early never costs a piece

Suppose the greedy cuts at position p, the FIRST place the balance returns to zero, and suppose some optimal cutting instead runs its first piece to q > p. Then s[0..p-1] is balanced and s[0..q-1] is balanced, so the middle part s[p..q-1] is balanced too, being the difference of two balanced prefixes.

So split that optimal first piece in two at p. Both halves are legal and the piece count went UP by one. Repeating the argument on the rest turns any cutting into the greedy one without ever losing a piece, which means the greedy is at least as good as any of them.

Splitting rather than swapping is what makes this argument short. It is the standard shape for "cut as soon as it is legal" problems, and it is the same argument #631 uses in the opposite direction.

## Why a zero balance is exactly a balanced piece

Between two consecutive zeros of the running balance, the balance starts and ends at zero, so the piece between them has equal counts. Nothing else needs checking, and in particular the balance may go negative in the middle, which is fine here: the question asks for equal counts, not for a bracket-style nesting. RRRRLLLL is one legal piece even though its balance dips to -4.

That distinction is the one to carry away. In #1043 a dip below zero is fatal; here it is irrelevant.

## Overflow

The answer is at most n / 2 = 100000, and the balance stays within plus or minus n. Nothing approaches the 32 bit limit of 2147483647.

## Cost

Time O(n). Space O(1).

Constraints - `2 ≤ length ≤ 200000` and the length is even - the line contains only `L` and `R`, in equal numbers