Minimum Number of Moves to Make Palindrome solution and explanation
IBM
6 more videos on this problem
2193. Minimum Number of Moves to Make Palindrome || Biweekly Contest 73 || Leetcode 2193Bro Coders · 12:44 · 12K views
MINIMUM NUMBER OF MOVES TO MAKE PALINDROME | LEETCODE 2193 | PYTHON SOLUTIONCracking FAANG · 14:47 · 6K views
2193. Minimum Number of Moves to Make Palindrome (Leetcode Hard)Programming Live with Larry · 20:17 · 2K views
【每日一题】LeetCode 2193. Minimum Number of Moves to Make PalindromeHuifeng Guan · 1:00:23 · 1K views
Leetcode 2193. Minimum Number of Moves to Make Palindrome (greedy)LetsCode · 13:39 · 279 views
Minimum Number of Moves to Make Palindrome - LeetCode 2193 | Best Intuition + Easy ApproachCodehurdle · 26:24 · 176 views
LeetCode 2193: Minimum Number of Moves to Make PalindromeAlitaCode · 27:09 · 20 views
The problem
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 <= 2000sconsists only of lowercase English letters.scan 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.
def min_moves_to_make_palindrome(s):
chars = list(s)
start, end = 0, len(s) - 1
moves = 0
while start < end:
if chars[start] == chars[end]:
start += 1
end -= 1
else:
k = end
while k > start and chars[k] != chars[start]:
k -= 1
if k == start: # No match found
chars[start], chars[start + 1] = chars[start + 1], chars[start]
moves += 1
else: # Match found
for i in range(k, end):
chars[i], chars[i + 1] = chars[i + 1], chars[i]
moves += 1
start += 1
end -= 1
return moves
print("Minimum moves:", min_moves_to_make_palindrome("letelt"))public class Solution {
public int minSwapsToMakePalindrome(String s) {
char[] arr = s.toCharArray();
int left = 0, right = s.length() - 1, moves = 0;
while (left < right) {
if (arr[left] == arr[right]) {
left++;
right--;
} else {
int k = right;
while (k > left && arr[k] != arr[left])
k--;
if (k == left) {
char temp = arr[left];
arr[left] = arr[left + 1];
arr[left + 1] = temp;
moves++;
} else {
for (int i = k; i < right; i++) {
char temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
moves++;
}
left++;
right--;
}
}
}
return moves;
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println("Minimum moves: " + sol.minSwapsToMakePalindrome("aabb"));
}
}#include <iostream>
#include <string>
#include <algorithm>
int minMovesToMakePalindrome(std::string s) {
int n = s.size();
int start = 0, end = n - 1, moves = 0;
while (start < end) {
if (s[start] == s[end]) {
start++;
end--;
} else {
int k = end;
while (k > start && s[k] != s[start])
k--;
if (k == start) {
std::swap(s[start], s[start + 1]);
moves++;
} else {
for (int i = k; i < end; i++) {
std::swap(s[i], s[i + 1]);
moves++;
}
start++;
end--;
}
}
}
return moves;
}
int main() {
std::string s = "letelt";
std::cout << "Minimum moves: " << minMovesToMakePalindrome(s) << std::endl;
return 0;
}function minMovesToMakePalindrome(s) {
let chars = s.split('');
let left = 0, right = chars.length - 1, moves = 0;
while (left < right) {
if (chars[left] === chars[right]) {
left++;
right--;
} else {
let k = right;
while (k > left && chars[k] !== chars[left]) {
k--;
}
if (k === left) {
[chars[left], chars[left + 1]] = [chars[left + 1], chars[left]];
moves++;
} else {
for (let i = k; i < right; i++) {
[chars[i], chars[i + 1]] = [chars[i + 1], chars[i]];
moves++;
}
left++;
right--;
}
}
}
return moves;
}
console.log("Minimum moves:", minMovesToMakePalindrome("letelt"));#include <stdio.h>
#include <string.h>
int min_moves_to_palindrome(char *s) {
int len = strlen(s);
int front = 0, back = len - 1, moves = 0;
while (front < back) {
if (s[front] == s[back]) {
front++;
back--;
} else {
int left = front, right = back;
while (s[left] != s[back]) {
left++;
}
if (left == back) {
s[left] = s[left - 1]; // This handles odd middle element
moves++;
back--;
} else {
while (left > front) {
char temp = s[left];
s[left] = s[left - 1];
s[left - 1] = temp;
left--;
moves++;
}
front++; back--;
}
}
}
return moves;
}
int main() {
char s[] = "aabb";
printf("Minimum moves: %d\n", min_moves_to_palindrome(s));
return 0;
}using System;
public class Solution {
public int MinMovesToMakePalindrome(string s) {
char[] arr = s.ToCharArray();
int left = 0, right = arr.Length - 1, moves = 0;
while (left < right) {
if (arr[left] == arr[right]) {
left++;
right--;
} else {
int k = right;
while (k > left && arr[k] != arr[left])
k--;
if (k == left) {
arr[left] = arr[left + 1];
moves++;
} else {
for (int i = k; i < right; i++) {
char temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
moves++;
}
left++;
right--;
}
}
}
return moves;
}
public static void Main(string[] args) {
Solution sol = new Solution();
Console.WriteLine("Minimum moves: " + sol.MinMovesToMakePalindrome("aabb"));
}
}In Python, this solution uses a list to easily handle character swapping, employing a strategy to bring mismatched elements together using greedy swaps.
Time Complexity: O(n^2); Space Complexity: O(n) from list representation of string.
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.
def min_moves_to_make_palindrome(s):
chars = list(s)
start, end = 0, len(s) - 1
moves = 0
while start < end:
if chars[start] == chars[end]:
start += 1
end -= 1
else:
k = end
while k > start and chars[k] != chars[start]:
k -= 1
if k == start: # No match found
chars[start], chars[start + 1] = chars[start + 1], chars[start]
moves += 1
else: # Match found
for i in range(k, end):
chars[i], chars[i + 1] = chars[i + 1], chars[i]
moves += 1
start += 1
end -= 1
return moves
print("Minimum moves:", min_moves_to_make_palindrome("letelt"))public class Solution {
public int minSwapsToMakePalindrome(String s) {
char[] arr = s.toCharArray();
int left = 0, right = s.length() - 1, moves = 0;
while (left < right) {
if (arr[left] == arr[right]) {
left++;
right--;
} else {
int k = right;
while (k > left && arr[k] != arr[left])
k--;
if (k == left) {
char temp = arr[left];
arr[left] = arr[left + 1];
arr[left + 1] = temp;
moves++;
} else {
for (int i = k; i < right; i++) {
char temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
moves++;
}
left++;
right--;
}
}
}
return moves;
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println("Minimum moves: " + sol.minSwapsToMakePalindrome("aabb"));
}
}#include <iostream>
#include <string>
#include <algorithm>
int minMovesToMakePalindrome(std::string s) {
int n = s.size();
int start = 0, end = n - 1, moves = 0;
while (start < end) {
if (s[start] == s[end]) {
start++;
end--;
} else {
int k = end;
while (k > start && s[k] != s[start])
k--;
if (k == start) {
std::swap(s[start], s[start + 1]);
moves++;
} else {
for (int i = k; i < end; i++) {
std::swap(s[i], s[i + 1]);
moves++;
}
start++;
end--;
}
}
}
return moves;
}
int main() {
std::string s = "letelt";
std::cout << "Minimum moves: " << minMovesToMakePalindrome(s) << std::endl;
return 0;
}function minMovesToMakePalindrome(s) {
let chars = s.split('');
let left = 0, right = chars.length - 1, moves = 0;
while (left < right) {
if (chars[left] === chars[right]) {
left++;
right--;
} else {
let k = right;
while (k > left && chars[k] !== chars[left]) {
k--;
}
if (k === left) {
[chars[left], chars[left + 1]] = [chars[left + 1], chars[left]];
moves++;
} else {
for (let i = k; i < right; i++) {
[chars[i], chars[i + 1]] = [chars[i + 1], chars[i]];
moves++;
}
left++;
right--;
}
}
}
return moves;
}
console.log("Minimum moves:", minMovesToMakePalindrome("letelt"));#include <stdio.h>
#include <string.h>
int min_moves_to_palindrome(char *s) {
int len = strlen(s);
int front = 0, back = len - 1, moves = 0;
while (front < back) {
if (s[front] == s[back]) {
front++;
back--;
} else {
int left = front, right = back;
while (s[left] != s[back]) {
left++;
}
if (left == back) {
s[left] = s[left - 1];
moves++;
back--;
} else {
while (left > front) {
char temp = s[left];
s[left] = s[left - 1];
s[left - 1] = temp;
left--;
moves++;
}
front++;
back--;
}
}
}
return moves;
}
int main() {
char s[] = "aabb";
printf("Minimum moves: %d\n", min_moves_to_palindrome(s));
return 0;
}using System;
public class Solution {
public int MinMovesToMakePalindrome(string s) {
char[] arr = s.ToCharArray();
int left = 0, right = arr.Length - 1, moves = 0;
while (left < right) {
if (arr[left] == arr[right]) {
left++;
right--;
} else {
int k = right;
while (k > left && arr[k] != arr[left])
k--;
if (k == left) {
arr[left] = arr[left + 1];
moves++;
} else {
for (int i = k; i < right; i++) {
char temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
moves++;
}
left++;
right--;
}
}
}
return moves;
}
public static void Main(string[] args) {
Solution sol = new Solution();
Console.WriteLine("Minimum moves: " + sol.MinMovesToMakePalindrome("aabb"));
}
}Python versions the frequency accord alike front-to-back ordeal, borrowing incremental insights over the middle clusters, advancing streamlined matches under pair-wise tweaks.
Time Complexity: O(n^2); Space Complexity: O(n) exists from list allocation during stepped restructuring efforts.
Approach 3: Default Approach
func minMovesToMakePalindrome(s string) int {
cs := []byte(s)
ans, n := 0, len(s)
for i, j := 0, n-1; i < j; i++ {
even := false
for k := j; k != i; k-- {
if cs[i] == cs[k] {
even = true
for ; k < j; k++ {
cs[k], cs[k+1] = cs[k+1], cs[k]
ans++
}
j--
break
}
}
if !even {
ans += n/2 - i
}
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Two Pointer Approach with Greedy Swapping | Time Complexity: O(n^2); Space Complexity: O(n) from list representation of string. |
| Character Frequency and Pairing | Time Complexity: O(n^2); Space Complexity: O(n) exists from list allocation during stepped restructuring efforts. |
| Default Approach | – |
Complexity analysis
| 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. |
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.