Problems
Red balls (R) and blue balls (B) are placed in a line. You want to rearrange them so that balls of the same color are adjacent.
Movement Rules
If there is a contiguous block of balls of the other color next to a ball, you can jump over the whole block in one move.
Example: A red ball can jump over an adjacent block of blue balls in one move, and vice versa.
You must choose only one color to move throughout the process.
If you start moving red balls, all subsequent moves must involve red balls.
Similarly, if you start moving blue balls, all subsequent moves must involve blue balls.
Example
If you move red balls first, you can gather all reds in 2 moves.
If you move blue balls first, you may need 4 moves.
Task
Given a line of balls, find the minimum number of moves needed to group the same color balls together following the above rules.
Input
The first line contains the total number of balls, N (1 ≤ N ≤ 500,000).
The second line contains a string of length N consisting of R and B, representing the balls' colors.
If the string contains only one color, the answer is
0.
Output
Print the minimum number of moves to group the balls of the same color together.
Subtask
| # | Score | Condition |
|---|---|---|
| #1 | 15 | N ≤ 10. |
| #2 | 22 | N ≤ 1,000. |
| #3 | 14 | N ≤ 500,000 and all blue balls are initially contiguous |
| #4 | 49 | Original constraints, no other restrictions |
Example #1
9
RBBBRBRRR
2
Example #2
8
BBRBBBBR
1
You must sign in to write code.