Connection Status:
Competition Arena > LittleElephantAndBallsAgain

LittleElephantAndBallsAgain

SRM 595 · 2013-06-25 · by Witaliy

SRM 595 · 2013-06-25 · by Witaliy · Brute Force
Class Name: LittleElephantAndBallsAgain
Return Type: int
Method Name: getNumber
Arg Types: (string)
Problem Statement

Problem Statement

Little Elephant from the Zoo of Lviv likes balls. He has some balls arranged in a row. Each of those balls has one of three possible colors: red, green, or blue.

You are given a String S. This string represents all the balls that are initially in the row (in the order from left to right). Red, green, and blue balls are represented by characters 'R', 'G', and 'B', respectively. In one turn Little Elephant can remove either the first ball in the row, or the last one.

Little Elephant wants to obtain a row in which all balls have the same color. Return the smallest number of turns in which this can be done.

Constraints

  • S will contain between 1 and 50 characters, inclusive.
  • S will consist only of characters 'R', 'G' and 'B'.
Examples
0)
"RRGGBB"
Returns: 4

One possible optimal solution is to remove 2 balls from the front and 2 from the back. The total number of turns is 2+2 = 4. After those 4 turns only green balls remained on the table.

1)
"R"
Returns: 0

You don't need to do any turns in this case, so the answer is 0.

2)
"RGBRGB"
Returns: 5

In any optimal solution only one of these six balls will remain on the table.

3)
"RGGGBB"
Returns: 3
4)
"RGBRBRGRGRBBBGRBRBRGBGBBBGRGBBBBRGBGRRGGRRRGRBBBBR"
Returns: 46

Submissions are judged against all 75 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class LittleElephantAndBallsAgain with a public method int getNumber(string S) · 75 test cases · 2 s / 256 MB per case

Submitting as anonymous