668. The Smallest Palindrome You Can Make
Change as FEW characters as possible to turn the word into a palindrome. Among all the ways that use the fewest changes, print the alphabetically smallest result.
egcfe -> efcfe
abcd -> abba
seven -> neven
## The fewest changes is forced
Positions i and n-1-i must end up equal. If they already are, nothing need be done; if they
differ, at least one of the two must change.
So the minimum is exactly the number of mismatched pairs, and there is no freedom in HOW MANY changes to make. The only freedom is WHICH of the two characters to keep in each mismatched pair.
## The smallest result takes the smaller letter
The pairs are independent: changing one pair never affects another. And within a pair, keeping the SMALLER of the two letters makes the earlier position smaller, which is what decides alphabetical order.
So set both characters of a mismatched pair to min(s[i], s[n-1-i]).
seven becomes neven: the pair is s and n, and n is smaller, so the s changes rather
than the n.
## Why "earlier position" is the right tiebreak
Alphabetical order compares left to right and stops at the first difference. The left member of each pair is always the earlier position, so making it as small as possible dominates anything that happens later.
Since the pairs do not interact, doing that for every pair independently gives the smallest overall word.
## The middle character
An odd-length word has a middle character paired with itself. It always matches, so it is never changed, and no special case is needed.
## The sweep
Converge from both ends, and on a mismatch write the smaller letter into both positions. One
pass, O(1) extra memory.
## Boundaries
A word that is already a palindrome comes back unchanged, with zero changes. A single character is already a palindrome.
## Cost
Time O(n). Space O(n) for the output.
Constraints - `1 ≤ length ≤ 200000` - the word contains only lowercase letters
Input
One line containing a non-empty word of lowercase letters.
Output
Print the resulting word on one line.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.