Minimum Number of Moves to Make Palindrome

Hard
776.

Minimum Number of Moves to Make Palindrome

Minimum Number of Moves to Make Palindrome is a hard coding problem on strings, greedy and two pointers, asked in Amazon, Google, Rubrik and Directi interviews.

In one move you may swap two adjacent characters of s. The input is guaranteed to be rearrangeable into a palindrome.

Return the minimum number of moves needed to make s a palindrome.

Example 1

Input
s = "aabb"
Output
2
Explanation
"aabb" → "abab" → "abba".

Example 2

Input
s = "letelt"
Output
2
Explanation
"letelt" → "letelt" → "lettel".

Example 3

Input
s = "kaiak"
Output
0
Explanation
Already a palindrome.

Constraints

  • 1 <= s.length <= 2000
  • s consists of lowercase English letters.
  • s can be rearranged to form a palindrome.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var minMovesToMakePalindrome = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Number of Moves to Make Palindrome — Solution

Minimum Number of Moves to Make Palindrome solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Minimum Number of Moves to Make Palindrome is a hard coding problem on strings, greedy and two pointers, asked in Amazon, Google, Rubrik and Directi interviews.

Problem statement

In one move you may swap two adjacent characters of s. The input is guaranteed to be rearrangeable into a palindrome.

Return the minimum number of moves needed to make s a palindrome.

Example 1

Input: s = "aabb"
Output: 2
Explanation: "aabb" → "abab" → "abba".

Example 2

Input: s = "letelt"
Output: 2
Explanation: "letelt" → "letelt" → "lettel".

Example 3

Input: s = "kaiak"
Output: 0
Explanation: Already a palindrome.

Constraints

  • 1 <= s.length <= 2000
  • s consists of lowercase English letters.
  • s can be rearranged to form a palindrome.

Hints for Minimum Number of Moves to Make Palindrome

  1. Hint 1

    Fix the outermost pair first: whatever ends up at both ends costs the same wherever it comes from.

  2. Hint 2

    For the leftmost character, its cheapest partner is the rightmost occurrence of that same character.

  3. Hint 3

    A character with no partner is the palindrome's centre — nudge it one step inward and carry on.

How to solve Minimum Number of Moves to Make Palindrome

Work from the outside in. For the character now at the left end, find its rightmost match and bubble that match to the right end; the swaps used are exactly its distance from the end. A character with no match anywhere else is the odd one out and only ever needs to drift toward the centre.

Approach

  1. Keep pointers i at the left and j at the right of the unsettled region.
  2. Scan k from j down to i looking for arr[k] == arr[i].
  3. If k > i, bubble it to position j with j - k adjacent swaps, then shrink both pointers.
  4. If k == i the character is unmatched: swap it one step right, count one move, and retry the same i.

Why it works

Choosing the rightmost match is optimal because any other occurrence of that character lies further left and would need at least as many swaps, and the swaps never disturb the relative order of the characters still to be paired. The unmatched character is unique (the string is rearrangeable), so pushing it inward one step at a time is exactly the cost of moving it to the centre.

Complexity

  • Time — O(n²)
  • Space — O(n)

Pitfalls

  • Matching the leftmost occurrence of the character costs more and gives a wrong answer.
  • When the unmatched character is found, i must not advance — the same position needs a new partner search.
  • Counting moves as index differences after several bubbles double-counts; count each adjacent swap as it happens.

Reference solution

Python

def minMovesToMakePalindrome(s: str) -> int:
    arr = list(s)
    moves = 0
    i, j = 0, len(arr) - 1
    while i < j:
        k = j
        while k > i and arr[k] != arr[i]:
            k -= 1
        if k == i:
            arr[i], arr[i + 1] = arr[i + 1], arr[i]
            moves += 1
        else:
            while k < j:
                arr[k], arr[k + 1] = arr[k + 1], arr[k]
                k += 1
                moves += 1
            i += 1
            j -= 1
    return moves

Java

public static int minMovesToMakePalindrome(String s) {
    char[] arr = s.toCharArray();
    int moves = 0, i = 0, j = arr.length - 1;
    while (i < j) {
        int k = j;
        while (k > i && arr[k] != arr[i]) k--;
        if (k == i) {
            char t = arr[i];
            arr[i] = arr[i + 1];
            arr[i + 1] = t;
            moves++;
        } else {
            while (k < j) {
                char t = arr[k];
                arr[k] = arr[k + 1];
                arr[k + 1] = t;
                k++;
                moves++;
            }
            i++;
            j--;
        }
    }
    return moves;
}

C++

int minMovesToMakePalindrome(string s) {
    int moves = 0, i = 0, j = (int) s.size() - 1;
    while (i < j) {
        int k = j;
        while (k > i && s[k] != s[i]) k--;
        if (k == i) {
            swap(s[i], s[i + 1]);
            moves++;
        } else {
            while (k < j) {
                swap(s[k], s[k + 1]);
                k++;
                moves++;
            }
            i++;
            j--;
        }
    }
    return moves;
}

JavaScript

var minMovesToMakePalindrome = function(s) {
    var arr = s.split("");
    var moves = 0, i = 0, j = arr.length - 1, t;
    while (i < j) {
        var k = j;
        while (k > i && arr[k] !== arr[i]) k--;
        if (k === i) {
            t = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = t;
            moves++;
        } else {
            while (k < j) {
                t = arr[k]; arr[k] = arr[k + 1]; arr[k + 1] = t;
                k++;
                moves++;
            }
            i++;
            j--;
        }
    }
    return moves;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Greedy Algorithms