Split the Signal Into Balanced Pieces

EasyGreedy

Problem

A signal is recorded as a string of L and R pulses. A piece of the signal is balanced when it contains as many Ls as Rs. The whole signal is balanced.

Cut the signal into contiguous balanced pieces (every pulse belongs to exactly one piece) and return the maximum number of pieces.

Example 1

Input:
signal = "RLRRLLRLRL"
Output:
4

RL | RRLL | RL | RL.

Example 2

Input:
signal = "RLRRRLLRLL"
Output:
2

RL | RRRLLRLL; the second piece has no balanced prefix shorter than itself.

Constraints

  • 2 ≤ signal.length ≤ 10^5
  • signal contains only 'L' and 'R'
  • signal is balanced

Hint

Show the first hint

Keep a running balance: +1 for R, -1 for L.

Walkthrough

How to approach it

01Clarify before coding

  • Must pieces be contiguous? Yes, and together they cover the whole signal.
  • Is the whole signal guaranteed balanced? Yes, so at least one piece always exists.
  • Are other characters possible? No, only L and R.

02Brute force

Try every set of cut positions and keep the largest set whose pieces are all balanced.

Cost: O(2^n · n): exponential.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.