Training Site
Sideways banner

Flower Garden

Input: Standard Input (stdin)
Output: Standard Output (stdout)
Memory limit: 128 megabytes
Time limit: 1.0 seconds

Hannah's flower garden is a row of N flowers. All of the flowers in her garden are either red, green, or blue in colour.

She would like to replace some of these flowers so that no two neighbouring flowers share the same colour.

A single replacement consists of replacing any flower with a new flower of a different colour (either red, green, or blue).

Please help Hannah find the minimum number of replacements required.


The first line contains a single integer N, the number of flowers in Hannah's garden.

The second line contains a string of length N, representing the colours of the flowers in the garden in order from left to right. Each character of the string is either 'R', 'G', or 'B', corresponding to red, green, and blue respectively.


You should print a single integer – the minimum number of replacements required to change the garden in such a way that no two neighbouring flowers share the same colour.


For all subtasks, 1 \le N \le 100.

  • Subtask 1 (30%): All flowers are the same colour.
  • Subtask 2 (30%): No flower shares the same colour as both of its neighbours.
  • Subtask 3 (40%): No further constraints apply.

Sample Explanation

In the first sample case, only a single replacement is necessary – the garden can be changed to "RGR" or "RBR" by replacing the second flower with either a green or blue flower.

In the second sample case, at least two replacements are required. One possible solution is to change the third flower to blue, and the fourth flower to green, resulting in "RGBGB".

  • Sample Input 1


    Sample Output 1

  • Sample Input 2


    Sample Output 2