We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Number of Moves to Make Palindrome

Difficulty: Hard

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.

Key Insights

  • A palindrome reads the same forwards and backwards.
  • The problem can be solved using a two-pointer technique.
  • The goal is to bring characters to their respective positions in a palindrome configuration.
  • Each swap of adjacent characters counts as one move.
  • The process involves identifying mismatches and counting the required moves to resolve them.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve the problem, we can utilize a two-pointer approach. We'll start with pointers at both ends of the string and move towards the center. The idea is to compare the characters at the two pointers. If they are the same, we move both pointers inward. If they are different, we need to make moves to bring the characters to the correct positions:

  1. Initialize two pointers, one at the start (left) and one at the end (right) of the string.
  2. While the left pointer is less than the right pointer:
    • If the characters at these pointers are the same, move both pointers inward.
    • If they are different, find the matching character from the other end and count the number of swaps needed to bring it next to the left pointer. This involves moving the left pointer to the right, or the right pointer to the left.
  3. Return the total count of moves needed.

This approach ensures that we efficiently compute the minimum number of moves required to transform the string into a palindrome.

Code Solutions

def minMovesToMakePalindrome(s: str) -> int:
    left, right = 0, len(s) - 1
    moves = 0
    s = list(s)  # Convert string to list for mutability

    while left < right:
        if s[left] == s[right]:
            left += 1
            right -= 1
        else:
            l, r = left, right
            while r > l and s[r] != s[left]:
                r -= 1
            if r == l:  # If no match found
                # Swap to make a match
                s[left], s[left + 1] = s[left + 1], s[left]
                moves += 1
            else:
                # Move the matching character to the right position
                for i in range(r, right):
                    s[i], s[i + 1] = s[i + 1], s[i]
                    moves += 1
                left += 1
                right -= 1
    return moves
← Back to All Questions