Bob 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. There are at most 26 types of people in Bob's class, lettered A
through Z
. Any two people with the same type and are standing next to one another are able to form a friendship. Bob 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 maximum number of friendships Bob can make?
Input Specification
First line: a string comprised of uppercase English characters indicating the types of each of Bob's classmates.
Output Specification
One integer: the maximum number of friendships Bob can make.
Constraints
Sample Input
BACCDABC
Sample Output
4
Explanation for Sample Case
Bob can rearrange the class line into CCCDBBAA
and make 4
friendships: two among the C
s, one between the B
s, and one between the A
s.
Comments