Minimum Number of Moves to Make Palindrome

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. For example, if the input is "aabb", the output is 2. "letelt" should give 2 as well.

# Minimum Moves to Make a Palindrome

## Problem Description

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: "aabb" -> "abab" -> "abba".
• We can obtain "baab" from s in 2 moves: "aabb" -> "abab" -> "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 "letelt" -> "letetl" -> "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.

## Brute Force Solution

A brute force solution would involve generating all possible permutations of the string `s` and checking if each permutation is a palindrome. If a permutation is a palindrome, we calculate the number of swaps required to transform the original string into that palindrome. Finally, we return the minimum number of swaps among all palindromic permutations.

However, this approach is highly inefficient because the number of permutations grows factorially with the length of the string (O(n!)).  Therefore, this approach is impractical for strings of even moderate length.

## Optimal Solution

The optimal solution involves a greedy approach combined with tracking the indices of characters that need to be moved. The basic idea is to work from the outside towards the center of the string, finding matching characters and moving them to their appropriate positions with the minimum number of swaps. Here's a step-by-step breakdown:

1.  **Find Matching Characters:** Iterate from the beginning and end of the string simultaneously. For each character at the beginning, find a matching character at the end.
2.  **Move Character:** If a matching character is found at the end, move it to its correct position adjacent to the character at the end. The number of swaps required is the distance the character needs to be moved.
3.  **Handle Odd Length Strings:** If no matching character is found for a character at the beginning, it means we are at the middle of the string (for odd length strings). In this case, move the middle character to the center of the string.
4.  **Repeat:** Repeat the process for the remaining inner part of the string.

Here's the Python code implementing this approach:

```python
def min_moves_palindrome(s):
    s = list(s)
    n = len(s)
    moves = 0

    for i in range(n // 2):
        for j in range(n - 1 - i, i, -1):
            if s[i] == s[j]:
                for k in range(j, n - 1 - i):
                    s[k], s[k + 1] = s[k + 1], s[k]
                    moves += 1
                break
    return moves

# Example usage:
s1 = "aabb"
print(f'Minimum moves for "aabb": {min_moves_palindrome(s1)}')  # Output: 2

s2 = "letelt"
print(f'Minimum moves for "letelt": {min_moves_palindrome(s2)}')  # Output: 2

s3 = "abab"
print(f'Minimum moves for "abab": {min_moves_palindrome(s3)}') # Output: 1

Big(O) Run-time Analysis

• The outer loop runs n/2 times, where n is the length of the string.
• The inner loop (searching for the matching character) can run up to n times in the worst case.
• The swapping loop can also run up to n times in the worst case.

Therefore, the overall time complexity is O(n^2).

Big(O) Space Usage Analysis

• The space complexity is O(n) because we convert the input string to a list of characters.
• We are modifying the list in place, so we don't need any extra space proportional to the input size.

Edge Cases and How to Handle Them

1. Empty String: If the input string is empty, it's already a palindrome, so we return 0.
2. Single Character String: If the input string contains only one character, it's also a palindrome, so we return 0.
3. String That Cannot Be Made a Palindrome: The problem statement guarantees that the input string can be converted into a palindrome. However, if that wasn't the case, you would need to add a check to see if the string can be made a palindrome at the beginning (e.g., by counting character frequencies).
4. String with All Same Characters: A string consisting of the same characters (e.g., "aaaa") is already a palindrome and requires 0 moves.
5. String with One Unique Character: If there is a string where all characters are identical, except for one, the greedy algorithm functions correctly by moving the unique character to the center with the least amount of swaps.