Minimum Number of Moves to Make Palindrome

Problem#

You may swap any two adjacent characters. Return the minimum number of such swaps to make s a palindrome. The input is guaranteed to be rearrangeable.

Examples#

"aabb" → 2 (aabb → abab → abba or via the right side).
"letelt" → 2.

Constraints#

1 <= s.length <= 2000.

Hints#

Hint 1

For each pair of converging pointers, the closer matching character should come in — greedy on smaller cost.

Approach#

Two pointers l, r. If s[l] == s[r] they’re already paired — shrink. Otherwise, find a j from the right with s[j] == s[l] and bubble it leftward to r via adjacent swaps, costing r - j moves. If no such j exists (the leftmost character is the unique odd one in an odd-length string), bubble s[l] one step right and re-check. This greedy choice always matches the cheaper end first.

Solution#

class Solution {
public:
    int minMovesToMakePalindrome(string s) {
        int moves = 0;
        int l = 0, r = s.size() - 1;
        while (l < r) {
            if (s[l] == s[r]) { ++l; --r; continue; }
            int j = r;
            while (j > l && s[j] != s[l]) --j;
            if (j == l) {
                // s[l] is the unique middle character — bubble it one right.
                swap(s[l], s[l + 1]);
                ++moves;
            } else {
                for (int k = j; k < r; ++k) swap(s[k], s[k + 1]);
                moves += r - j;
                ++l; --r;
            }
        }
        return moves;
    }
};

func minMovesToMakePalindrome(s string) int {
    b := []byte(s)
    moves := 0
    l, r := 0, len(b)-1
    for l < r {
        if b[l] == b[r] {
            l++
            r--
            continue
        }
        j := r
        for j > l && b[j] != b[l] {
            j--
        }
        if j == l {
            b[l], b[l+1] = b[l+1], b[l]
            moves++
        } else {
            for k := j; k < r; k++ {
                b[k], b[k+1] = b[k+1], b[k]
            }
            moves += r - j
            l++
            r--
        }
    }
    return moves
}

class Solution:
    def minMovesToMakePalindrome(self, s: str) -> int:
        b = list(s)
        moves = 0
        l, r = 0, len(b) - 1
        while l < r:
            if b[l] == b[r]:
                l += 1
                r -= 1
                continue
            j = r
            while j > l and b[j] != b[l]:
                j -= 1
            if j == l:
                b[l], b[l + 1] = b[l + 1], b[l]
                moves += 1
            else:
                for k in range(j, r):
                    b[k], b[k + 1] = b[k + 1], b[k]
                moves += r - j
                l += 1
                r -= 1
        return moves

function minMovesToMakePalindrome(s) {
    const b = s.split('');
    let moves = 0;
    let l = 0, r = b.length - 1;
    while (l < r) {
        if (b[l] === b[r]) { l++; r--; continue; }
        let j = r;
        while (j > l && b[j] !== b[l]) j--;
        if (j === l) {
            [b[l], b[l + 1]] = [b[l + 1], b[l]];
            moves++;
        } else {
            for (let k = j; k < r; k++) {
                [b[k], b[k + 1]] = [b[k + 1], b[k]];
            }
            moves += r - j;
            l++;
            r--;
        }
    }
    return moves;
}

class Solution {
    public int minMovesToMakePalindrome(String s) {
        char[] b = s.toCharArray();
        int moves = 0;
        int l = 0, r = b.length - 1;
        while (l < r) {
            if (b[l] == b[r]) { l++; r--; continue; }
            int j = r;
            while (j > l && b[j] != b[l]) j--;
            if (j == l) {
                char tmp = b[l]; b[l] = b[l + 1]; b[l + 1] = tmp;
                moves++;
            } else {
                for (int k = j; k < r; k++) {
                    char t = b[k]; b[k] = b[k + 1]; b[k + 1] = t;
                }
                moves += r - j;
                l++;
                r--;
            }
        }
        return moves;
    }
}

function minMovesToMakePalindrome(s: string): number {
    const b = s.split('');
    let moves = 0;
    let l = 0, r = b.length - 1;
    while (l < r) {
        if (b[l] === b[r]) { l++; r--; continue; }
        let j = r;
        while (j > l && b[j] !== b[l]) j--;
        if (j === l) {
            [b[l], b[l + 1]] = [b[l + 1], b[l]];
            moves++;
        } else {
            for (let k = j; k < r; k++) {
                [b[k], b[k + 1]] = [b[k + 1], b[k]];
            }
            moves += r - j;
            l++;
            r--;
        }
    }
    return moves;
}

Editorial#

The non-trivial proof obligation is why greedy works. Consider the two endpoints s[l], s[r]: in the optimal palindrome they pair with their counterparts somewhere in the string. Pairing s[l] with the rightmost matching character (and symmetrically s[r] with the leftmost) is always cheaper or equal — moving the closer match would later have to bring the farther one over the same distance. The middle-character special case handles the unique odd character in odd-length strings: it must end up in the center, so bubbling it one step right defers it without losing optimality.

Complexity#

Time: O(n²) — each pair may scan and shift up to n characters.
Space: O(1).

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#