Minimum Number of Moves to Make Palindrome

hard two pointers greedy string

Problem

You are given a string s of lowercase letters. In one move you may swap any two adjacent characters. Return the minimum number of moves needed to make s a palindrome. The input is guaranteed to be rearrangeable into a palindrome.

Inputs = "aabb"

Output2

"aabb" → "abab" → "abba": two adjacent swaps reach a palindrome.

Inputs = "letelt"

Output2

One reachable palindrome is "lettel"; it cannot be done in fewer than 2 moves.

s (lowercase letters, rearrangeable into a palindrome)

def min_moves_to_palindrome(s):
    chars = list(s)
    moves = 0
    left, right = 0, len(chars) - 1
    while left < right:
        k = right
        while k > left and chars[k] != chars[left]:
            k -= 1
        if k == left:
            chars[left], chars[left + 1] = chars[left + 1], chars[left]
            moves += 1
        else:
            while k < right:
                chars[k], chars[k + 1] = chars[k + 1], chars[k]
                k += 1
                moves += 1
            left += 1
            right -= 1
    return moves

function minMovesToPalindrome(s) {
  const chars = s.split("");
  let moves = 0;
  let left = 0, right = chars.length - 1;
  while (left < right) {
    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 {
      while (k < right) {
        [chars[k], chars[k + 1]] = [chars[k + 1], chars[k]];
        k++;
        moves++;
      }
      left++;
      right--;
    }
  }
  return moves;
}

int minMovesToPalindrome(String s) {
    char[] chars = s.toCharArray();
    int moves = 0;
    int left = 0, right = chars.length - 1;
    while (left < right) {
        int k = right;
        while (k > left && chars[k] != chars[left]) k--;
        if (k == left) {
            char t = chars[left]; chars[left] = chars[left + 1]; chars[left + 1] = t;
            moves++;
        } else {
            while (k < right) {
                char t = chars[k]; chars[k] = chars[k + 1]; chars[k + 1] = t;
                k++;
                moves++;
            }
            left++;
            right--;
        }
    }
    return moves;
}

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

Explanation

A palindrome is symmetric, so the character we put at the very left must equal the character at the very right. We fix the string from the outside in using two pointers, left and right, and a running moves counter.

At each round we keep chars[left] fixed and scan inward from right with index k until we find its twin. The greedy insight is that the nearest matching character should be the one paired with left — pairing any farther match would only cost extra swaps.

Once the twin is found at index k, we bubble it to position right with adjacent swaps. Each swap moves it one cell, so it costs exactly right - k moves. Then both ends are settled, so we do left++ and right-- and repeat on the smaller inner window.

If the scan reaches k == left, then chars[left] has no partner left in the window — it is the single odd-count character that belongs in the middle. We swap it one step toward the center (cost 1) and retry without moving the pointers, letting it drift to the middle over later rounds.

For s = "mamad": pair the leading m with the m at index 2, bubbling it to the end in 2 swaps to reach "maadm"; then pair the a's in 1 more swap to reach "madam" — a palindrome in 3 moves total.

Time: O(n²) Space: O(n)