While Valentine's Day may be an exciting day for couples and to-be couples, it can be quite the opposite for the single people out there! For Kevin, he's had enough of all the couples in his class, and so as the teacher's assistant, he decides to move everyone to a different seat. Fortunately for Kevin, his classroom seating is arranged as one giant circle, with the teacher and Kevin included. Thus, it can also be modelled as a single line, spanning from the seat immediately left of the teacher to the seat immediately right of the teacher.
To determine potential couples, every person in the class has a specific type. Any two people with the same type and are sitting next to one another will engage in, well, couple things (Kevin evidently does not share the same type as anyone else in his class). By rearranging the seating plan, what is the minimum number of couples Kevin can seat beside each other? Note that should a person sit beside two people of their type, there are technically two couples formed... though things might get weird.
Constraints
The length of the input string will not exceed characters.
Input Specification
The first and only line of input contains a string comprised of uppercase English characters indicating the types of each of Kevin's classmates.
Output Specification
Output one integer, the minimum number of couples Kevin's seating plan has sitting beside each other.
Sample Input 1
BACCDABC
Output for Sample Input 1
0
Explanation for Sample Case 1
Kevin can rearrange the class seating into CABCADCB
and make couples sit beside each other, since no adjacent people share a common type.
Sample Input 2
ZZZZZ
Output for Sample Input 2
4
Explanation for Sample Case 2
No matter how Kevin rearranges the class, there will be couples. Evidently, this is not Kevin's class.
Comments