{x}
blog image

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.

 

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.

 

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.

Solution Explanation:

This problem asks for the minimum number of moves to make a given string a palindrome by swapping adjacent characters. The solution leverages a two-pointer approach combined with a greedy strategy.

Approach:

  1. Initialization: The string s is converted into a character array cs. Two pointers, i (starting from the beginning) and j (starting from the end), are used to iterate through the string. ans variable keeps track of the minimum moves.

  2. Iterative Search: The outer loop continues as long as i is less than j. For each character at index i, the inner loop searches from j towards i for a matching character.

  3. Swap and Move: If a matching character is found at index k, the inner loop swaps adjacent characters to move the matching character to position j. The number of swaps is added to ans. Then, j is decremented to move towards the center.

  4. Unmatched Character Handling: If no matching character is found, it implies that the character at index i needs to be moved to the other side of the palindrome, requiring n/2 - i swaps, where n is the length of the string. This is because the character has to be moved across the center.

  5. Return: Finally, the function returns ans, representing the minimum number of moves required.

Time Complexity: O(n^2), where n is the length of the string. The nested loops contribute to the quadratic time complexity in the worst case (e.g., all characters are unique).

Space Complexity: O(n), due to the use of a character array cs. In some languages this might be implicitly handled and not take extra space.

Code Explanation (Python):

class Solution:
    def minMovesToMakePalindrome(self, s: str) -> int:
        cs = list(s)  # Convert string to list for easier swapping
        ans, n = 0, len(s)  # Initialize moves count and string length
        i, j = 0, n - 1    # Initialize pointers
 
        while i < j:
            even = False  # Flag to check if a matching character is found
            for k in range(j, i, -1):  # Search for matching character from j to i
                if cs[i] == cs[k]:
                    even = True
                    while k < j:  # Swap to move the matching character to position j
                        cs[k], cs[k + 1] = cs[k + 1], cs[k]
                        k += 1
                        ans += 1
                    j -= 1  # Decrement j after finding a match
                    break
 
            if not even:  # If no matching character is found
                ans += n // 2 - i  # Move the character to the other side
 
            i += 1  # Increment i
        return ans

The other languages (Java, C++, Go) follow a very similar structure and logic, adapting the syntax accordingly. The core algorithm remains the same.