2017 PSUT Coding Marathon |
---|
Finished |
There are N balloons linked together in a line. Each balloon is either red, green, or blue. Mr. Light wants to get exactly one balloon of each color (exactly one red balloon, one green balloon, and one blue balloon) - no more or less. Find the minimum number of cuts he has to make to achieve this.
This picture illustrates the first sample test case: "RRGRGRRB". Each letter represents one of the three colors. After making these cuts, Mr. Light will get the two balloons "GR" and the last balloon "B".
Note that the three balloons Mr. Light will get don't have to be disconnected, and it is only allowed to cut the rope that links the balloons together.
The input contains a string S (3 ≤ |S| ≤ 2 × 105), representing the balloons in the line. Each letter is either 'R', 'G', or 'B' and represents the color of that balloon.
It is guaranteed that for each color, there exists at least one balloon with that color.
Print the minimum number of cuts on a single line.
RRGRGRRB
3
RGRGBB
2
Name |
---|