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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Number of Moves to Make Palindrome

Number: 1356

Difficulty: Hard

Paid? No

Companies: Amazon, Meta, Microsoft

Problem Description

Given a string s consisting only of lowercase English letters, return the minimum number of adjacent swap moves needed to rearrange s into a palindrome. It is guaranteed that a palindromic rearrangement is always possible.

Key Insights

  • Use a two-pointer approach starting from the outer ends of the string.
  • If the characters at the two pointers match, move both pointers inward.
  • If they do not match, search between the pointers for a matching character.
  • Count adjacent swaps to shift the found matching character to the desired position.
  • If no matching character is found (i.e. in case of a middle unique character for odd-length palindromes), swap it toward the center.

Space and Time Complexity

Time Complexity: O(n^2) in the worst-case scenario due to nested scanning and adjacent swaps. Space Complexity: O(n) for converting the string into a mutable list (if using languages where strings are immutable).

Solution

The solution uses a greedy two pointers algorithm along with a simulation of adjacent swaps. We convert the given string into a list for efficient updates. Start with two pointers (left and right) at the beginning and end of the list. For each pair:

  • If the characters match, move both pointers inward.
  • If they do not match, iterate from the right pointer towards the left to find a character matching the left pointer's character.
    • When found, perform a series of adjacent swap operations to bring that matching character to the right pointer.
    • Count each swap.
  • If no matching character is found, swap the character at the left pointer with its adjacent neighbor to gradually move the unmatched unique character toward the middle. This greedy approach ensures that we make a local optimal move on every step, resulting in the minimization of the total moves necessary.

Code Solutions

# Python solution with detailed comments
def minMovesToMakePalindrome(s: str) -> int:
    # Convert string to list for mutable swaps
    chars = list(s)
    moves = 0
    left, right = 0, len(chars) - 1
    
    # Process until the two pointers meet or cross
    while left < right:
        # If the two characters are the same, move inward
        if chars[left] == chars[right]:
            left += 1
            right -= 1
        else:
            # Find matching character for chars[left] from right side
            matching = right
            while matching > left and chars[matching] != chars[left]:
                matching -= 1
            
            # If matching pointer reached left, then char at left is unique
            if matching == left:
                # Swap the unique character forward by one
                chars[left], chars[left+1] = chars[left+1], chars[left]
                moves += 1
            else:
                # Bring the matching char to the end by adjacent swaps
                while matching < right:
                    chars[matching], chars[matching+1] = chars[matching+1], chars[matching]
                    moves += 1
                    matching += 1
                left += 1
                right -= 1
    return moves

# Example usage:
s = "aabb"
print(minMovesToMakePalindrome(s))  # Expected output: 2
← Back to All Questions