Swapping Seats
Time limit2sMemory limit512 MB
Given a circular string of A, B, C, find the minimum number of seat swaps needed so each letter forms one contiguous block.
- Level
Hard8 of 10
- Topics
- Greedy, Sliding window, String, Combinatorics
- Solved
- No attempts yet
Problem
N people are sitting at a circular table for a long session of negotiations. Each person belongs to one of three groups: A, B, or C. A group is happy if all of its members sit contiguously in a block of consecutive seats. You want to make all groups happy using a sequence of swap operations. In each swap operation, two people exchange seats with each other. What is the minimum number of swaps required to make all groups happy?
Input
The input consists of a single line containing N characters (1 ≤ N ≤ 1 000 000), each of which is A, B, or C. The i-th character denotes the group of the person initially sitting at the i-th seat of the table, where seats are numbered in clockwise order.
Output
Output a single integer, the minimum possible number of swaps.