LCC '22 Contest 4 S2 - Leon's Friends

View as PDF

Submit solution

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

Author:
Problem type

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 1 and at most 2 \times 10^5 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 0 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 4 friendships made.


Comments

There are no comments at the moment.