LCC '23 Contest 4 S2 - Couples Fever

View as PDF

Submit solution

Points: 7
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type

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 2 \times 10^5 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 0 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 4 couples. Evidently, this is not Kevin's class.


Comments

There are no comments at the moment.