# Minimum Number of Moves to Make Palindrome
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-number-of-moves-to-make-palindrome)
Canonical: https://scaleengineer.com/dsa/problems/minimum-number-of-moves-to-make-palindrome
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** String, Binary Indexed Tree
---
## Problem
You are given a string `s` consisting only of lowercase English letters.

In one **move**, you can select any two **adjacent** characters of `s` and swap them.

Return _the **minimum number of moves** needed to make_ `s` _a palindrome_.

**Note** that the input will be generated such that `s` can always be converted to a palindrome.

**Example 1:**

**Input:** s = "aabb"
**Output:** 2
**Explanation:**
We can obtain two palindromes from s, "abba" and "baab". 
- We can obtain "abba" from s in 2 moves: "a**ab**b" -> "ab**ab**" -> "abba".
- We can obtain "baab" from s in 2 moves: "a**ab**b" -> "**ab**ab" -> "baab".
Thus, the minimum number of moves needed to make s a palindrome is 2.

**Example 2:**

**Input:** s = "letelt"
**Output:** 2
**Explanation:**
One of the palindromes we can obtain from s in 2 moves is "lettel".
One of the ways we can obtain it is "lete**lt**" -> "let**et**l" -> "lettel".
Other palindromes such as "tleelt" can also be obtained in 2 moves.
It can be shown that it is not possible to obtain a palindrome in less than 2 moves.

**Constraints:**

* `1 <= s.length <= 2000`
* `s` consists only of lowercase English letters.
* `s` can be converted to a palindrome using a finite number of moves.

# Approaches
## Simple Greedy Simulation
This approach uses a greedy strategy with two pointers, `left` and `right`, to build the palindrome from the outside in. We iterate as long as `left` is less than `right`. In each step, we try to match the character at the `left` pointer with a corresponding character and move it to the `right` pointer's position. If the character at `left` is the unique middle character of the palindrome (meaning it has no pair), we simply swap it with its right neighbor to shift it towards the center and re-evaluate.
**Time:** O(N^2), where N is the length of the string. The `while` loop runs about N/2 times. Inside the loop, finding the matching character `k` can take up to O(N) time, and the subsequent swaps can also take O(N) time in the worst case. · **Space:** O(N), where N is the length of the string. This is required to create a mutable character array from the immutable input string.
**Pros:** The logic is relatively straightforward to understand and implement.; It correctly solves the problem by making locally optimal moves.; It modifies the string representation in-place (using a char array), which simplifies state management.
**Cons:** The time complexity is quadratic, which might be slow for very large inputs, although it passes within the given constraints.; Handling the middle character by single swaps can be less efficient than directly placing it or working around it.
### Explanation
The core idea is to iteratively fix the outermost characters of the string to form a palindrome. We use a character array for easy in-place modifications.

We maintain two pointers, `left` and `right`, starting at the ends of the array. 
- If `arr[left]` and `arr[right]` are already a match, we've found a pair for our palindrome, so we can shrink our problem space by moving the pointers inwards.
- If they don't match, we are committed to making `arr[left]` the character for the current outer pair. We search for its matching partner from the right side of the array (from `right-1` down to `left`).
- If we find a partner at index `k`, we calculate the number of adjacent swaps needed to move it to the `right` position, which is `right - k`. We add this to our total moves and perform the swaps. After this, `arr[left]` and `arr[right]` match, so we shrink the pointers.
- A special case occurs when the search for a partner for `arr[left]` only finds itself (`k == left`). This indicates `arr[left]` is the character that will end up in the middle of the final odd-length palindrome. Since it can't be paired, we perform a minimal action to get it out of the `left` position: we swap it with `arr[left+1]`, add 1 to our move count, and let the loop continue from the same `left` and `right` pointers. This process effectively nudges the middle character towards the center one step at a time while other pairs are being formed.

```java
class Solution {
    public int minMovesToMakePalindrome(String s) {
        char[] arr = s.toCharArray();
        int n = arr.length;
        int left = 0;
        int right = n - 1;
        int moves = 0;

        while (left < right) {
            if (arr[left] == arr[right]) {
                left++;
                right--;
                continue;
            }

            // Find the rightmost character that matches arr[left]
            int k = right - 1;
            while (k > left && arr[k] != arr[left]) {
                k--;
            }

            if (k == left) { // arr[left] is the middle character
                // Swap with its right neighbor
                char temp = arr[left];
                arr[left] = arr[left + 1];
                arr[left + 1] = temp;
                moves++;
            } else { // Found a pair for arr[left] at index k
                // Move character from k to right
                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;
    }
}
```
### Algorithm
1. Initialize `moves = 0`.
2. Convert the input string `s` to a mutable representation, like a character array `arr`.
3. Use two pointers, `left = 0` and `right = s.length() - 1`.
4. Loop while `left < right`:
   a. If `arr[left]` and `arr[right]` are the same, they form a valid pair. Shrink the window by incrementing `left` and decrementing `right`.
   b. If they are different, find the rightmost index `k` of the character `arr[left]` within the current window `[left, right]`.
   c. **Case 1: A pair is found (`k != left`)**. This means `arr[k]` is the matching character for `arr[left]`. We need to move `arr[k]` to the `right` position. This requires `right - k` adjacent swaps. Add this number to `moves`, perform the swaps (by bubbling the character at `k` to the right), and then shrink the window (`left++`, `right--`).
   d. **Case 2: No pair is found (`k == left`)**. This implies that `arr[left]` is the unique middle character of the palindrome. Since it has no pair, we cannot match it. Instead, we swap it with its adjacent character `arr[left+1]` to move it out of the way. This costs 1 move. We do **not** shrink the window, as we haven't formed a pair yet. The loop continues, and in the next iteration, the new `arr[left]` will be processed.

## Optimized Greedy Two-Pointer Simulation
This approach is a more refined greedy strategy. At each step where the outer characters `s[left]` and `s[right]` do not match, we evaluate two possible greedy moves. The first option is to find the matching pair for `s[left]` and move it to the `right` end. The second option is to find the matching pair for `s[right]` and move it to the `left` end. We calculate the number of swaps required for both options and execute the one that is cheaper. This ensures that we make the most efficient move at each step to form the palindrome's outer layers.
**Time:** O(N^2). Although it makes smarter choices, the asymptotic complexity remains the same. The `while` loop runs N/2 times, and each iteration involves two linear scans (O(N)) and a series of swaps (O(N)). · **Space:** O(N), for the mutable character array.
**Pros:** More efficient in practice than the simple greedy approach by always making the locally optimal choice.; Handles the middle character case more elegantly and directly without special logic.; Guaranteed to find the minimum number of moves due to the nature of the greedy choice.
**Cons:** The time complexity is still quadratic, same as the simpler greedy approach.; The implementation is slightly more complex due to considering two options at each step.
### Explanation
This method also builds the palindrome from the outside in but makes a more informed greedy choice at each step. When `arr[left]` and `arr[right]` differ, we don't just default to matching `arr[left]`. Instead, we calculate the 'cost' of two alternative actions:

1.  **Match `arr[left]`**: We find the rightmost occurrence of `arr[left]`'s character, say at index `k`. The cost to move this character to position `right` is `right - k` swaps.
2.  **Match `arr[right]`**: We find the leftmost occurrence of `arr[right]`'s character, say at index `j`. The cost to move this character to position `left` is `j - left` swaps.

We then choose the action with the minimum cost. If `right - k` is less than or equal to `j - left`, we perform the first action. Otherwise, we perform the second. After the chosen character is moved and the pair is formed, we shrink the window by incrementing `left` and decrementing `right`.

This approach elegantly handles the middle character case. If `arr[left]` is the middle character, its only occurrence is at `left`, so `k` will be `left`. The cost `right - k` will be large. The other character `arr[right]` must have a pair, and the cost `j - left` to move its pair will likely be smaller, leading the algorithm to correctly choose the second, more efficient option.

```java
class Solution {
    public int minMovesToMakePalindrome(String s) {
        char[] arr = s.toCharArray();
        int n = arr.length;
        int left = 0;
        int right = n - 1;
        int moves = 0;

        while (left < right) {
            if (arr[left] == arr[right]) {
                left++;
                right--;
                continue;
            }

            // Find rightmost match for left char
            int k = right - 1;
            while (k > left && arr[k] != arr[left]) {
                k--;
            }

            // Find leftmost match for right char
            int j = left + 1;
            while (j < right && arr[j] != arr[right]) {
                j++;
            }

            // Choose the cheaper move
            if ((right - k) <= (j - left)) {
                moves += (right - k);
                // Move char from k to right
                for (int i = k; i < right; i++) {
                    char temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                }
            } else {
                moves += (j - left);
                // Move char from j to left
                for (int i = j; i > left; i--) {
                    char temp = arr[i];
                    arr[i] = arr[i - 1];
                    arr[i - 1] = temp;
                }
            }
            left++;
            right--;
        }
        return moves;
    }
}
```
### Algorithm
1. Initialize `moves = 0`.
2. Convert the input string `s` to a character array `arr`.
3. Use two pointers, `left = 0` and `right = s.length() - 1`.
4. Loop while `left < right`:
   a. If `arr[left] == arr[right]`, shrink the window (`left++`, `right--`).
   b. Otherwise, we have two choices to form the outer pair:
      i. Match `arr[left]`: Find its rightmost partner at index `k`. The cost is `right - k` swaps.
      ii. Match `arr[right]`: Find its leftmost partner at index `j`. The cost is `j - left` swaps.
   c. Compare the costs. If moving `arr[left]`'s partner is cheaper or equal (`right - k <= j - left`), then:
      - Add `right - k` to `moves`.
      - Bubble the character from `k` to `right`.
   d. Otherwise (moving `arr[right]`'s partner is cheaper):
      - Add `j - left` to `moves`.
      - Bubble the character from `j` to `left`.
   e. After the swaps, a pair is formed at the boundaries. Shrink the window (`left++`, `right--`).

# Solutions
### Java

```java
class Solution {
public
  int minMovesToMakePalindrome(String s) {
    int n = s.length();
    int ans = 0;
    char[] cs = s.toCharArray();
    for (int i = 0, j = n - 1; i < j; ++i) {
      boolean even = false;
      for (int k = j; k != i; --k) {
        if (cs[i] == cs[k]) {
          even = true;
          for (; k < j; ++k) {
            char t = cs[k];
            cs[k] = cs[k + 1];
            cs[k + 1] = t;
            ++ans;
          }
          --j;
          break;
        }
      }
      if (!even) {
        ans += n / 2 - i;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minMovesToMakePalindrome(string s) {
    int n = s.size();
    int ans = 0;
    for (int i = 0, j = n - 1; i < j; ++i) {
      bool even = false;
      for (int k = j; k != i; --k) {
        if (s[i] == s[k]) {
          even = true;
          for (; k < j; ++k) {
            swap(s[k], s[k + 1]);
            ++ans;
          }
          --j;
          break;
        }
      }
      if (!even)
        ans += n / 2 - i;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def minMovesToMakePalindrome(self, s: str) -> int: cs = list(s) ans, n = 0, len(s) i, j = 0, n - 1 while i < j: even = False for k in range(j, i, - 1): if cs[i] == cs[k]: even = True while k < j: cs[k], cs[k + 1] = cs[k + 1], cs[k] k += 1 ans += 1 j -= 1 break if not even: ans += n // 2 - i i += 1 return ans

```