Scale Engineer

Minimum Number of Moves to Make Palindrome

Hard
#1998Time: O(N^2), where N is the length of the string. The `while` loop runs about N/2 times. Inside the loop, finding the matching character `k` can take up to O(N) time, and the subsequent swaps can also take O(N) time in the worst case.Space: O(N), where N is the length of the string. This is required to create a mutable character array from the immutable input string.
Patterns
Two PointersGreedy
Data structures
StringBinary Indexed Tree

Prompt

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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses a greedy strategy with two pointers, left and right, to build the palindrome from the outside in. We iterate as long as left is less than right. In each step, we try to match the character at the left pointer with a corresponding character and move it to the right pointer's position. If the character at left is the unique middle character of the palindrome (meaning it has no pair), we simply swap it with its right neighbor to shift it towards the center and re-evaluate.

Algorithm

  1. Initialize moves = 0.
  2. Convert the input string s to a mutable representation, like a character array arr.
  3. Use two pointers, left = 0 and right = s.length() - 1.
  4. Loop while left < right: a. If arr[left] and arr[right] are the same, they form a valid pair. Shrink the window by incrementing left and decrementing right. b. If they are different, find the rightmost index k of the character arr[left] within the current window [left, right]. c. Case 1: A pair is found (k != left). This means arr[k] is the matching character for arr[left]. We need to move arr[k] to the right position. This requires right - k adjacent swaps. Add this number to moves, perform the swaps (by bubbling the character at k to the right), and then shrink the window (left++, right--). d. Case 2: No pair is found (k == left). This implies that arr[left] is the unique middle character of the palindrome. Since it has no pair, we cannot match it. Instead, we swap it with its adjacent character arr[left+1] to move it out of the way. This costs 1 move. We do not shrink the window, as we haven't formed a pair yet. The loop continues, and in the next iteration, the new arr[left] will be processed.

Walkthrough

The core idea is to iteratively fix the outermost characters of the string to form a palindrome. We use a character array for easy in-place modifications.

We maintain two pointers, left and right, starting at the ends of the array.

  • If arr[left] and arr[right] are already a match, we've found a pair for our palindrome, so we can shrink our problem space by moving the pointers inwards.
  • If they don't match, we are committed to making arr[left] the character for the current outer pair. We search for its matching partner from the right side of the array (from right-1 down to left).
  • If we find a partner at index k, we calculate the number of adjacent swaps needed to move it to the right position, which is right - k. We add this to our total moves and perform the swaps. After this, arr[left] and arr[right] match, so we shrink the pointers.
  • A special case occurs when the search for a partner for arr[left] only finds itself (k == left). This indicates arr[left] is the character that will end up in the middle of the final odd-length palindrome. Since it can't be paired, we perform a minimal action to get it out of the left position: we swap it with arr[left+1], add 1 to our move count, and let the loop continue from the same left and right pointers. This process effectively nudges the middle character towards the center one step at a time while other pairs are being formed.
class Solution {    public int minMovesToMakePalindrome(String s) {        char[] arr = s.toCharArray();        int n = arr.length;        int left = 0;        int right = n - 1;        int moves = 0;         while (left < right) {            if (arr[left] == arr[right]) {                left++;                right--;                continue;            }             // Find the rightmost character that matches arr[left]            int k = right - 1;            while (k > left && arr[k] != arr[left]) {                k--;            }             if (k == left) { // arr[left] is the middle character                // Swap with its right neighbor                char temp = arr[left];                arr[left] = arr[left + 1];                arr[left + 1] = temp;                moves++;            } else { // Found a pair for arr[left] at index k                // Move character from k to right                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;    }}

Complexity

Time

O(N^2), where N is the length of the string. The `while` loop runs about N/2 times. Inside the loop, finding the matching character `k` can take up to O(N) time, and the subsequent swaps can also take O(N) time in the worst case.

Space

O(N), where N is the length of the string. This is required to create a mutable character array from the immutable input string.

Trade-offs

Pros

  • The logic is relatively straightforward to understand and implement.

  • It correctly solves the problem by making locally optimal moves.

  • It modifies the string representation in-place (using a char array), which simplifies state management.

Cons

  • The time complexity is quadratic, which might be slow for very large inputs, although it passes within the given constraints.

  • Handling the middle character by single swaps can be less efficient than directly placing it or working around it.

Solutions

class Solution {public  int minMovesToMakePalindrome(String s) {    int n = s.length();    int ans = 0;    char[] cs = s.toCharArray();    for (int i = 0, j = n - 1; i < j; ++i) {      boolean even = false;      for (int k = j; k != i; --k) {        if (cs[i] == cs[k]) {          even = true;          for (; k < j; ++k) {            char t = cs[k];            cs[k] = cs[k + 1];            cs[k + 1] = t;            ++ans;          }          --j;          break;        }      }      if (!even) {        ans += n / 2 - i;      }    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem