Minimum Number of Moves to Make Palindrome — Hard Problem & Solution

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

Difficulty: Hard
Topics: Strings, Greedy, Two Pointers
Asked at: Amazon, Google, Directi
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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.

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

Keep pointers i at the left and j at the right of the unsettled region.
Scan k from j down to i looking for arr[k] == arr[i].
If k > i, bubble it to position j with j - k adjacent swaps, then shrink both pointers.
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

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue