Minimum Swaps to Group Recruitment Seats

In the IT industry, the demand for talent is ever increasing. At a beach recruitment event, the three industry giants – Baidu, Alibaba, and Tencent (collectively known as BAT) – have set up their recruitment booths in a random interleaving order, e.g., ABABTATT. Because the companies are fighting for free seating, their seats are mixed up. This makes the arrangement awkward for the applicants.

The management now requires that the seats be rearranged by swapping pairs of seats (each swap switches exactly two seats) so that every company’s seats become consecutive. In other words, a valid final arrangement could be BBAAATTT or AAABBTTT (or any permutation in which the seats of the same company are together).

Your task is: Given the current seating arrangement, compute the minimum number of swaps needed so that the seats for each company are grouped together.

The solution involves trying all possible orders of the three companies and, for each order, selecting contiguous segments whose lengths equal the number of seats for each company. For a given permutation, let the segments be denoted as 1, 2, 3 corresponding to the companies in that order. Let mis[i][j] be the number of seats in segment i that actually belong to company j (where j is not the intended company for segment i). Then a direct swap between segment i and j can fix min(mis[i][j], mis[j][i]) misplacements. After performing all possible direct swaps, the remaining misplacements form cycles which require 2 swaps per 3 misplaced seats. With the total number of misplacements denoted by M and the sum of direct swaps by D, the minimum number of swaps is:

[ \text{swaps} = D + 2\times\frac{(M - 2D)}{3} ]

Your program should compute the minimum swap count over all possible group orders.

inputFormat

The input consists of a single line containing a string. The string is made up of characters 'A', 'B', and 'T', which represent the seating arrangement for Alibaba, Baidu, and Tencent respectively.

outputFormat

Output an integer representing the minimum number of swaps required to group the seats of each company together.

sample

ABABTATT

2