Bob's Friends

View as PDF

Submit solution

Points: 5
Time limit: 1.0s
Memory limit: 64M
Java 128M
PyPy 2 128M
PyPy 3 128M

Problem type

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.


1 \le |S| \le 2 \times 10^5

Sample Input


Sample Output


Explanation for Sample Case

Bob can rearrange the class line into CCCDBBAA and make 4 friendships: two among the Cs, one between the Bs, and one between the As.


There are no comments at the moment.