Watch 7 video solutions for Minimum Number of Moves to Make Palindrome, a hard level problem involving Two Pointers, String, Greedy. This walkthrough by Bro Coders has 11,980 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a string s consisting only of lowercase English letters.
In one move, you can select any two adjacent characters of s and swap them.
Return the minimum number of moves needed to make s a palindrome.
Note that the input will be generated such that s can always be converted to a palindrome.
Example 1:
Input: s = "aabb" Output: 2 Explanation: We can obtain two palindromes from s, "abba" and "baab". - We can obtain "abba" from s in 2 moves: "aabb" -> "abab" -> "abba". - We can obtain "baab" from s in 2 moves: "aabb" -> "abab" -> "baab". Thus, the minimum number of moves needed to make s a palindrome is 2.
Example 2:
Input: s = "letelt" Output: 2 Explanation: One of the palindromes we can obtain from s in 2 moves is "lettel". One of the ways we can obtain it is "letelt" -> "letetl" -> "lettel". Other palindromes such as "tleelt" can also be obtained in 2 moves. It can be shown that it is not possible to obtain a palindrome in less than 2 moves.
Constraints:
1 <= s.length <= 2000s consists only of lowercase English letters.s can be converted to a palindrome using a finite number of moves.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.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two Pointer Greedy Swapping | O(n²) | O(1) | Best for interviews and moderate string sizes; simple to implement and easy to reason about. |
| Character Pairing + Fenwick Tree | O(n log n) | O(n) | Large inputs where counting swaps efficiently matters; demonstrates advanced data structures. |