Minimum Number of Moves to Make Palindrome - Solution & Explanation

Problem Overview: Given a string s, you can swap only adjacent characters. The goal is to determine the minimum number of swaps required to rearrange the string into a palindrome. If the string can form a palindrome, compute the smallest number of adjacent moves needed.

Approach 1: Two Pointer Greedy Swapping (O(n²) time, O(1) space)

This approach uses two pointers starting from both ends of the string. If characters at left and right match, move both pointers inward. If they do not match, search from the right pointer toward the left to find a matching character for s[left]. Once found, repeatedly swap adjacent characters to move that match toward the right boundary. If no match exists, the current character must be the center of the palindrome, so swap it one step toward the middle and continue. The greedy idea is to always pair the closest valid match to minimize swap distance.

This simulation directly counts adjacent swaps and modifies the string in place. It works well for moderate input sizes and is easy to implement in languages like C++, Java, and Python. Because each mismatch can trigger multiple adjacent swaps, the worst‑case runtime reaches O(n²), while space remains constant.

Approach 2: Character Frequency and Pairing with Fenwick Tree (O(n log n) time, O(n) space)

A more optimized method treats the problem as counting how far characters must move to reach their mirrored positions. First validate that the character frequencies allow a palindrome (at most one odd count). Then build pair indices for each character from left and right occurrences. The goal becomes measuring how many positions each character must shift when forming the palindrome.

Use a Fenwick Tree (Binary Indexed Tree) to efficiently track how many positions have already been occupied or shifted. When placing each pair, query the tree to determine how many indices have moved before the current one, which translates to the number of adjacent swaps needed. Each update and query runs in O(log n), producing a total runtime of O(n log n) with O(n) auxiliary space.

This method separates pairing logic from swap counting and scales better for large strings. It combines ideas from string manipulation, greedy pairing, and inversion counting.

Recommended for interviews: The greedy two‑pointer solution is the most common expectation because it clearly demonstrates understanding of palindrome structure and adjacent swap mechanics. It is easier to reason about during a whiteboard discussion. The Fenwick Tree approach shows stronger algorithmic depth and optimization skills, especially if the interviewer asks how to reduce the quadratic behavior.