Minimum Moves to Rearrange String

You are given a string s consisting only of the characters 'a' and 'b'. Your task is to determine the minimum number of moves required to rearrange the characters so that no two adjacent characters are the same. In one move, you can swap any two characters in the string. If it is impossible to achieve such a rearrangement, output -1.

The problem can be approached by observing that a valid rearrangement exists only if the absolute difference between the counts of 'a' and 'b' is at most 1, i.e. $$|count_a - count_b| \le 1.$$

If a valid rearrangement exists, consider two possible alternating patterns:

• Pattern 1 (starting with 'a'): a b a b ...
• Pattern 2 (starting with 'b'): b a b a ...

Count the number of mismatches for each pattern, and the answer is the minimum number of swaps needed (each swap fixes two mismatches). Note that the number of required swaps is computed as the floor division of the number of mismatches by 2.

inputFormat

The input is a single line string s provided via standard input. The string only contains the characters 'a' and 'b'.

outputFormat

Output a single integer representing the minimum number of moves required. If rearrangement is impossible, output -1.

ab

0