Skills101
← All coding problems

Split into Balanced Strings

easyStrings II+10 XPTime limit 2s

A dance line is written as a string of L (left step) and R (right step). A piece is balanced if it has as many Ls as Rs. The whole string is balanced. Cut it into the largest possible number of consecutive pieces so that every piece is balanced.

RLRRLLRLRL can be cut into RL | RRLL | RL | RL — 4 pieces.

Input: one line with the string (only L and R, equal numbers of each).

Output: the maximum number of balanced pieces.

Constraints: 2 ≤ length ≤ 10⁵.

Think about it: keep a running balance (+1 for L, −1 for R). Every time it returns to 0, close a piece there — cutting as early as possible never hurts.

Sample input 1

RLRRLLRLRL

Sample output 1

4

Sample input 2

LLLRRR

Sample output 2

1

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…

Log in to run and submit your code — it's free.