|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|0.5 초||1024 MB||72||33||28||43.750%|
JOI-kun, an expert of home garden, grows vegetables of Joy grass in his home garden. In his garden, there are N flowerpots aligned in the east-west direction. These flowerpots are numbered by 1, . . . , N from the west end. There are N Joy grasses. In each flowerpot, there is one Joy grass planted.
In the spring, JOI-kun noticed that, against his expectations, Joy grasses had yielded leaves of various colors. Additionally, he discovered that Joy grasses had not grown as much as expected. He looked up books, and found the following facts:
Therefore, JOI-kun decided to rearrange flowerpots so that no Joy grasses with the same leaf color adjoin Flowerpots are so heavy that JOI-kun can only swap two Joy grasses in neighboring flowerpots in a single operation. In other words, what JOI-kun can do in a single operation is choosing an arbitrary flowerpot i (1 ≤ i ≤ N −1) and then swapping Joy grasses in flowerpots i and i + 1.
Write a program which, given the number of Joy grasses and the colors of them, calculates the minimum number of operations which are required to rearrange Joy grasses so that no Joy grasses with the same leaf color adjoin.
Read the following data from the standard input.
S is a string of length N. Its i-th (1 ≤ i ≤ N) character is
Y if the leaf color of the Joy grass in flowerpot i is red, green, and yellow, respectively.
Write a line containing the minimum number of required operations to the standard output. If it is impossible to rearrange Joy grasses so that no Joy grasses with the same leaf color adjoin, write −1 instead.
The following is a way to rearrange Joy grasses so that no Joy grasses with the same leaf color adjoin:
After this, the order of Joy grasses will be
RYRGY. Since it is impossible to rearrange Joy grasses with at most 1 operation, the answer is 2.
In this example, regardless of the operations, it is impossible to rearrange Joy grasses so that no Joy grasses with the same leaf color adjoin.