Skip to main content
Talentd

Minimum Number of Moves to Make Palindrome - Solution & Explanation

HardTwo PointersStringGreedyBinary Indexed Tree15 min readAsked at: Amazon, Microsoft, Goldman Sachs +2
Practice this problem

Problem Statement

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 <= 2000
  • s consists only of lowercase English letters.
  • s can be converted to a palindrome using a finite number of moves.

Approach Overview

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 1: Two Pointer Approach with Greedy Swapping

This approach uses two pointers to compare characters from the start and end of the string and swaps characters greedily to form the palindrome.

The idea is to bring mismatched pairs closer using adjacent swaps, minimizing their number by pairing characters optimally.

This implementation uses a while loop with two pointers, 'front' and 'back'. As it traverses, it tries to match characters from both ends. If they are not equal, it tracks the position from 'front' where a match with 'back' is found. Thereafter, swaps are made to align the characters, reducing the problem size until a palindrome is formed.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2), Space Complexity: O(1) - The algorithm iteratively checks pairs and swaps them in-place.

Try this approach in the editor →

Approach 2: Character Frequency and Pairing

This approach utilizes character frequencies to understand the remixing requirements more clearly and make calculated swaps based on character proximity and appearance balancing between left and right halves.

The main aim is minimizing disruptions by smartly realigning same-type characters adjoining each other strategically over the course.

The solution iteratively applies frequencies and positioning for pairing optimal positioning using greedy local optimizations swapping characters close range. The character mismatches are solved taking least distance matches.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2), Space Complexity: O(1), considering all pointers achieved manipulation without extra space.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Two Pointer Approach with Greedy Swapping

Time Complexity: O(n^2), Space Complexity: O(1) - The algorithm iteratively checks pairs and swaps them in-place.

Character Frequency and Pairing

Time Complexity: O(n^2), Space Complexity: O(1), considering all pointers achieved manipulation without extra space.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Two Pointer Greedy SwappingO(n²)O(1)Best for interviews and moderate string sizes; simple to implement and easy to reason about.
Character Pairing + Fenwick TreeO(n log n)O(n)Large inputs where counting swaps efficiently matters; demonstrates advanced data structures.

Video Solution

2193. Minimum Number of Moves to Make Palindrome || Biweekly Contest 73 || Leetcode 2193 • Bro Coders • 12,208 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is Minimum Number of Moves to Make Palindrome easy or hard?
Minimum Number of Moves to Make Palindrome is categorized as a Hard problem because it combines greedy reasoning with swap counting. While the basic simulation is straightforward, optimizing it with advanced structures like Fenwick Trees requires deeper algorithmic knowledge.
Minimum Number of Moves to Make Palindrome Python/Java solution
Python and Java implementations typically simulate the greedy two‑pointer process. Move inward from both ends, search for a matching character, and perform adjacent swaps to bring it to the correct side while counting the moves.
How to solve Minimum Number of Moves to Make Palindrome in O(n log n)?
Pair matching characters first and determine their target palindrome positions. Then use a Fenwick Tree (Binary Indexed Tree) to count how many indices have already shifted while placing characters. Each update and prefix query runs in O(log n), leading to an overall O(n log n) solution.
What is the best approach for Minimum Number of Moves to Make Palindrome?
The most common approach uses two pointers and greedy adjacent swaps. Start from both ends of the string, find matching characters, and swap them toward the correct position. This method runs in O(n^2) time with O(1) space and is typically expected in coding interviews.
Is Minimum Number of Moves to Make Palindrome asked at Google/Amazon/Meta?
Palindrome transformation and minimum swap problems appear frequently in interviews at companies like Amazon, Google, and Meta. Variants involving adjacent swaps, greedy pairing, or inversion counting are commonly used to evaluate string manipulation and algorithmic thinking.
What data structure is used in Minimum Number of Moves to Make Palindrome?
The basic solution uses a two‑pointer technique with greedy swaps on the string. Advanced solutions use a Binary Indexed Tree (Fenwick Tree) to efficiently count shifts or inversions while constructing the palindrome.
What is the time complexity of Minimum Number of Moves to Make Palindrome?
The standard greedy two‑pointer solution runs in O(n^2) time because mismatched characters may require multiple adjacent swaps. An optimized approach using a Binary Indexed Tree to count position shifts reduces the complexity to O(n log n) with O(n) space.

Ready to solve this problem?

Practice Minimum Number of Moves to Make Palindrome with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Insertion Steps to Make a String Palindrome

Next

Minimum Number of Flips to Make Binary Grid Palindromic I