1075. Fewest Swaps to Make It Alternate

A binary string is given. One move exchanges any two characters, not necessarily adjacent. Print the fewest moves needed so that no two neighbouring characters are equal, or -1 if it is impossible.

111000 -> 1 exchange positions 1 and 4, giving 101010 010 -> 0 already alternating 1110 -> -1 three ones and one zero cannot alternate 1100 -> 1 exchange positions 1 and 2, giving 1010

Positions are numbered from 0, and the two positions exchanged need not be next to one another. In 111000 an exchange of neighbours cannot finish the job in one move: swapping positions 2 and 3 gives 110100, which still has 11 at the front.

## What most people try first

Search over sequences of swaps, which is enormous, or over which positions to move, which double counts. Breadth first search over the 2^m strings is the brute force this problem was checked against for short inputs.

## Only two target strings exist

An alternating string of length m is determined entirely by its first character, so there are exactly two candidates: 1010... and 0101....

Counting the ones tells you which are possible:

* ones == zeros: both targets are reachable, try both * ones == zeros + 1: only the target starting with 1 * zeros == ones + 1: only the target starting with 0 * anything else: -1, since swapping never changes the counts

## The cost of a target

Compare the string with the target position by position and count the MISMATCHES. A mismatch is either a 0 where a 1 belongs or the other way round, and the two kinds occur equally often, because both strings have the same number of ones.

One swap can fix exactly two mismatches, one of each kind, and cannot fix more, since it touches only two positions. So

cost = mismatches / 2

and that is both a lower bound, because each swap repairs at most two, and achievable, because the two kinds pair up exactly.

## Why the counts decide feasibility

A swap exchanges two characters, so the number of ones never changes. An alternating string of even length has equal counts and one of odd length has one more of its leading character. So any string whose counts differ by more than 1 can never alternate, and 1110 is exactly that case.

## The trap

Counting mismatches and dividing by two WITHOUT first checking the counts. On 1110 against 1010 there are two mismatches, and dividing gives 1, which is nonsense: the two mismatched positions both hold a 1 where a 0 belongs, so no swap fixes either. The count check is not an optimisation, it is what makes the division meaningful.

## Overflow

Counts are bounded by the length, 100000. The 32 bit limit of 2147483647 is not in play.

## Cost

Time O(m). Space O(1).

Constraints - `1 ≤ length ≤ 100000` - the line contains only `0` and `1`