Code Implementation

class Solution:
    def minMovesToMakePalindrome(self, s: str) -> int:
        s = list(s)
        moves = 0
        left, right = 0, len(s) - 1
        while left < right:
            if s[left] == s[right]:
                left += 1
                right -= 1
            else:
                k = right
                while k > left and s[k] != s[left]:
                    k -= 1
                if k == left:
                    # No matching char, must move s[left] to the center
                    s[left], s[left+1] = s[left+1], s[left]
                    moves += 1
                else:
                    # Move s[k] to s[right]
                    for i in range(k, right):
                        s[i], s[i+1] = s[i+1], s[i]
                        moves += 1
                    left += 1
                    right -= 1
        return moves
      

class Solution {
public:
    int minMovesToMakePalindrome(string s) {
        int moves = 0;
        int left = 0, right = s.size() - 1;
        while (left < right) {
            if (s[left] == s[right]) {
                left++;
                right--;
            } else {
                int k = right;
                while (k > left && s[k] != s[left]) k--;
                if (k == left) {
                    // Move s[left] to the center
                    swap(s[left], s[left+1]);
                    moves++;
                } else {
                    for (int i = k; i < right; ++i) {
                        swap(s[i], s[i+1]);
                        moves++;
                    }
                    left++;
                    right--;
                }
            }
        }
        return moves;
    }
};
      

class Solution {
    public int minMovesToMakePalindrome(String s) {
        char[] arr = s.toCharArray();
        int moves = 0;
        int left = 0, right = arr.length - 1;
        while (left < right) {
            if (arr[left] == arr[right]) {
                left++;
                right--;
            } else {
                int k = right;
                while (k > left && arr[k] != arr[left]) k--;
                if (k == left) {
                    // Move arr[left] to the center
                    char temp = arr[left];
                    arr[left] = arr[left+1];
                    arr[left+1] = temp;
                    moves++;
                } else {
                    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;
    }
}
      

var minMovesToMakePalindrome = function(s) {
    s = s.split('');
    let moves = 0;
    let left = 0, right = s.length - 1;
    while (left < right) {
        if (s[left] === s[right]) {
            left++;
            right--;
        } else {
            let k = right;
            while (k > left && s[k] !== s[left]) k--;
            if (k === left) {
                // Move s[left] to the center
                [s[left], s[left+1]] = [s[left+1], s[left]];
                moves++;
            } else {
                for (let i = k; i < right; ++i) {
                    [s[i], s[i+1]] = [s[i+1], s[i]];
                    moves++;
                }
                left++;
                right--;
            }
        }
    }
    return moves;
};
      

Problem Description

Given a string s, you can perform the following operation any number of times: choose any character in s and move it to any position in the string (including the beginning or the end). Your task is to find the minimum number of moves needed to make s a palindrome. Each move consists of moving one character to a new position. The string consists of only lowercase English letters.

• There is always at least one way to make the string a palindrome.
• Each move counts as one, regardless of how far the character is moved.
• Do not reuse the same move for multiple characters; each move affects only one character at a time.

Thought Process

At first glance, one might consider brute-forcing all possible permutations of the string to check which ones are palindromes and then count the minimum moves. However, this quickly becomes impractical for longer strings due to the factorial growth in possibilities.

Instead, we notice that making a string a palindrome involves matching characters symmetrically from the outside in. If the characters at the current left and right positions match, we can leave them in place. If not, we need to find a matching character for one of them and move it into place, ideally with the fewest moves possible.

This leads us to a "greedy" or two-pointer approach: always try to match the leftmost and rightmost characters, and when they don't match, bring the nearest matching character into position using the minimum number of swaps (which correspond to moves).

The key insight is that moving a character to its correct position can be done by a series of adjacent swaps, each counting as one move. By always choosing the nearest possible match, we minimize the total moves.

Solution Approach

Let's break down the algorithm step by step:

1. Use two pointers: left at the start of the string and right at the end.
2. While left < right:
   • If s[left] == s[right], both characters are already matching for the palindrome. Move both pointers inward.
   • If not, search for a matching character for s[left] from right down to left+1:
     • If found at position k (s[k] == s[left]), move s[k] to position right by swapping it rightwards one position at a time. Each swap counts as one move.
     • If no match is found (i.e., k == left), it means s[left] is the unique middle character (for odd-length palindromes). Move it towards the center by swapping it with the next character, and count the move.
3. Repeat until the pointers cross.
4. The total number of swaps is the minimum number of moves needed.

This approach is efficient because:

• Each swap brings a character closer to its correct position.
• We only traverse the string once from both ends, making the process linear in the worst case.
• We handle the unique center character (for odd-length strings) gracefully.

Example Walkthrough

Let's walk through the example s = "aabb":

1. Initial String: a a b b
   left = 0, right = 3
   s[0] = 'a', s[3] = 'b' (not equal)
2. Search for 'a' from right to left. s[1] = 'a' (found at k=1).
3. Move s[1] to position 3 by swapping:
   • Swap s[1] and s[2]: a b a b (moves = 1)
   • Swap s[2] and s[3]: a b b a (moves = 2)
4. Now, left = 1, right = 2. s[1] = 'b', s[2] = 'b' (they match), so move inward.
5. Pointers cross. The string is now "abba", a palindrome, in 2 moves.

This demonstrates how the algorithm efficiently matches pairs and moves characters into place with the minimum number of moves.

Time and Space Complexity

Brute-force Approach:

• Time Complexity: O(n!), since it would consider all permutations of the string.
• Space Complexity: O(n!), due to storing all permutations.

• Time Complexity: O(n²), because for each character, in the worst case, we may need to scan up to n positions (though usually much less).
• Space Complexity: O(n), since we may need to work on a copy of the string as a list/array for swapping.

The optimized approach is efficient and practical for typical input sizes.

Summary

The key insight for this problem is recognizing that making a string into a palindrome is about pairing matching characters from the ends inward. By using a two-pointer approach and greedily moving the nearest matching character into place with adjacent swaps, we minimize the number of moves required. This strategy avoids the exponential complexity of brute-force methods and elegantly solves the problem with clear logic and efficient steps.