Prompt and setting
Every adjacent swap costs one. Characters may repeat, and the input can be impossible when more than one character has odd frequency. The goal is the minimum number of swaps, not merely any palindrome.
What the interviewer tests
- Deriving the odd-frequency feasibility condition.
- Matching the left character with the nearest viable partner from the right.
- Proving why the greedy choice is optimal and accounting for shifts.
Clarifying questions before answering
- Are swaps only adjacent, and does each swap cost one?
- Is the alphabet arbitrary, and are Unicode code points treated as characters?
- Should the function mutate an array or return only the count?
- What input size determines whether an O(n²) approach is acceptable?
30-second answer framework
Count odd frequencies first; more than one odd count makes a palindrome impossible. Use pointers at both ends. If the ends match, move inward. Otherwise find the matching character for the left end by scanning from the right boundary inward, bubble it toward the right with adjacent swaps, and count each move. If no match exists, the unmatched character must be the single center; move it toward the center and continue.
Step-by-step deep dive
1. Prove feasibility
A palindrome has at most one odd frequency, because pairs occupy symmetric positions and only an odd-length center can remain unpaired. This check avoids running the greedy loop on impossible input.
2. Match the boundaries
For pointers i and j, if s[i] equals s[j], both positions are fixed. Otherwise search k from j down to i + 1 for s[k] == s[i]. Moving that character right costs j - k swaps and preserves the already fixed prefix.
3. Handle the center character
If no match is found, s[i] is the odd-frequency character that belongs in the center. Move it one step right at a time until it reaches the middle, counting swaps. Do not discard it or assume the center must be found on the first pass.
4. Implement the simulation
count odd frequencies
if odd_count > 1: return impossible
left = 0, right = n - 1, swaps = 0
while left < right:
if s[left] == s[right]: left++, right--; continue
k = right
while k > left and s[k] != s[left]: k--
if k == left:
swap s[k] with s[k + 1]
swaps++
else:
while k < right:
swap s[k] with s[k + 1]
k++, swaps++
left++, right--
return swaps5. Analyze complexity and proof idea
Each search and bubbling pass can scan O(n), repeated O(n) times, so time is O(n²) and the mutable array uses O(1) extra space. The greedy partner is nearest to the boundary; moving a farther equal character would require at least as many swaps before the boundary can be fixed. The center case is forced by parity.
High-quality sample answer
“I first count odd frequencies; more than one means impossible. Then I compare the two ends. On a mismatch, I find the nearest equal character to the right boundary and bubble it into place, adding its distance; if no equal exists, that character is the unique odd center, so I move it toward the middle. Matching ends shrink the window. The simulation is O(n²) time and O(1) extra space, and the greedy choice is optimal because any farther partner needs at least as many adjacent swaps.”
Common mistakes
- Check only whether counts are even → odd-length strings may have one odd count → allow at most one odd frequency.
- Swap with an arbitrary matching character → extra movement can be non-minimal → choose the nearest partner to the boundary.
- Drop the unmatched character → the center move is undercounted → bubble it toward the middle.
- Use two-pointer swaps without shifting → adjacent-swap cost is lost → simulate every adjacent move or use an equivalent data structure.
Follow-up questions and responses
Can the algorithm return the palindrome too?
Yes. Keep the mutable array and return both its final contents and the swap count. The same simulation records each adjacent swap if the caller needs the sequence.
How would you improve large inputs?
Track original positions with a Fenwick tree or order-statistics structure so moving a character can update positions in logarithmic time. The greedy pairing remains, while the cost calculation avoids shifting every element.
What if swaps are arbitrary rather than adjacent?
That is a different cost model. The nearest-partner distance proof no longer applies; define the allowed operation before reusing this algorithm.