Fewest Swaps for a Palindrome
Only one operation is allowed: swap two ADJACENT characters. Print the fewest swaps
needed to make the string a palindrome, or -1 if it is impossible.
mamad -> 3
ntiin -> 1
asflkj -> -1
## When it is impossible
A palindrome has at most one character with an odd count, the one in the middle. Swapping
never changes any character's count, so if more than one character occurs an odd number of
times the answer is -1.
That check is necessary and sufficient for FEASIBILITY, and it must come first. Without it the greedy below loops forever looking for a partner that does not exist.
## The greedy
Work from both ends inward. At each step the two ends must agree:
lo = 0, hi = n-1, total = 0
while lo < hi:
if s[lo] == s[hi]: lo++; hi--; continue
find the largest k <= hi with s[k] == s[lo]
if k == lo:
# s[lo] is the odd character and belongs in the middle
swap it one step right, count 1, and retry this position
else:
bubble s[k] rightward to position hi, counting hi - k swaps
lo++; hi--
## Why matching the NEAREST partner from the right is optimal
Two claims.
First, the character at lo must end up paired with SOME equal character, and moving that
partner to hi costs its distance from hi. Choosing the RIGHTMOST occurrence minimises
that distance, so it is the cheapest partner for this position.
Second, the swaps used to move it do not interfere with later steps. Bubbling a character rightward past others preserves the relative order of everything it passes, so the multiset and the order of the untouched middle are exactly as they were, shifted by one position each.
Together those give an exchange argument: any optimal solution can be rewritten to make the same choice at this position without increasing the total.
## The odd-character case
When no partner exists to the right of lo, the character at lo is the unique
odd-count one and belongs in the centre. Moving it one step right and retrying is the
cheapest repair, because it must cross every position between here and the centre
eventually, and one swap makes progress.
aabbc answers 4, and it is the case that exercises this branch: the c starts at the end
and has to travel to the middle.
## Why a table is the wrong tool
The state would have to be the current arrangement, of which there are n!. There is no
useful smaller state, which is exactly why the exchange argument has to carry the whole
solution.
That is worth noticing as a diagnostic: when the natural state is a permutation, a DP is usually not the intended answer.
## How this was verified
The greedy was checked against a BREADTH-FIRST SEARCH over the graph of all strings reachable by adjacent swaps, taking the shortest distance to any palindrome. That oracle shares no reasoning with the greedy at all: it is a shortest-path computation over arrangements.
300 random strings, no disagreement. For a greedy whose correctness rests on an exchange argument I wrote myself, that is the level of checking the claim deserves.
## Boundaries
a answers 0 and aa answers 0. ab answers -1, two odd counts.
abcba answers 0, already a palindrome. aabb answers 2.
## Cost
Time O(n^2). Space O(n).