Leon gets bored whenever the class lines up to go to the washroom so he would like to make certain people in his class friends with each other. Every person's type is denoted by an uppercase English letter. Any two people with the same type and standing next to one another will form a friendship. Leon's teacher is getting tired of hearing the students talk with their friends and would like to minimize the number of friendships in the class. Leon has much influential power within his class and is able to rearrange the class line in any way he wants without adding people, removing people, or changing anyone's type. What is the minimum number of friendships Leon can make?
Input Specification
First line: a string comprised of uppercase English characters indicating the types of each of Leon's classmates.
Output Specification
One integer: the minimum number of friendships Leon can make.
Constraints
There are at least and at most students in Leon's class.
Sample Input 1
BACCDABC
Output for Sample Input 1
0
Explanation for Sample Case 1
Leon can rearrange the class line into CABCADCB
which makes friendships since no adjacent friends share a common type.
Sample Input 2
ZZZZZ
Output for Sample Input 2
4
Explanation for Sample Case 2
No matter how Leon rearranges the class, there will be friendships made.
Comments