Taro Logo

Minimum Number of Moves to Make Palindrome

Hard
Amazon logo
Amazon
2 views
Topics:
StringsGreedy AlgorithmsTwo Pointers

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: "aab<u>b</u>" -> "ab<u>ab</u>" -> "abba".
- We can obtain "baab" from s in 2 moves: "aa<u>b</u>b" -> "a<u>ba</u>b" -> "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<u>lt</u>" -> "let<u>et</u>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.

Solution


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. What is the maximum length of the input string?
  2. Can the input string contain characters other than lowercase English letters?
  3. If the input string cannot be converted to a palindrome, what should I return? For instance, should I return -1 or throw an exception?
  4. Are we only considering adjacent swaps to form the palindrome?
  5. If multiple solutions exist with the same minimum number of moves, is any one of them acceptable?

Brute Force Solution

Approach

The brute force way to find the fewest moves to make a string a palindrome involves exploring all possible swap combinations. We try every possible ordering of characters and, for each arrangement, check how many swaps are needed to turn it into a palindrome. Then, we pick the ordering that requires the fewest swaps.

Here's how the algorithm would work step-by-step:

  1. Consider every single possible arrangement of the string. Imagine you are shuffling a deck of cards and looking at every order they could be in.
  2. For each of those arrangements, figure out the minimum number of swaps it would take to make that arrangement a palindrome (reads the same forwards and backwards).
  3. Compare the number of swaps needed for each of the arrangements we looked at.
  4. The smallest number of swaps from any of those arrangements is your answer.

Code Implementation

import itertools

def minimum_moves_to_make_palindrome_brute_force(input_string):
    minimum_swaps = float('inf')

    # Generate all possible permutations of the string
    for permutation_tuple in itertools.permutations(input_string):
        permutation_string = ''.join(permutation_tuple)

        # Calculate swaps needed to make current permutation a palindrome
        swaps_needed = calculate_swaps_to_make_palindrome(permutation_string)

        # Track minimum swaps found so far
        minimum_swaps = min(minimum_swaps, swaps_needed)

    return minimum_swaps

def calculate_swaps_to_make_palindrome(input_string):
    string_list = list(input_string)
    swaps_count = 0
    left_index = 0
    right_index = len(string_list) - 1

    while left_index < right_index:
        if string_list[left_index] == string_list[right_index]:
            left_index += 1
            right_index -= 1
        else:
            # Find matching character from right side
            temporary_index = right_index
            while temporary_index > left_index and string_list[temporary_index] != string_list[left_index]:
                temporary_index -= 1

            # No matching character, string can't be palindrome
            if temporary_index == left_index:
                return float('inf')

            else:
                # Shift characters to make a match
                for index_to_shift in range(temporary_index, right_index):
                    string_list[index_to_shift], string_list[index_to_shift + 1] = string_list[index_to_shift + 1], string_list[index_to_shift]
                    swaps_count += 1

                left_index += 1
                right_index -= 1
    return swaps_count

Big(O) Analysis

Time Complexity
O(n! * n)The algorithm considers all possible permutations of the input string, which has a time complexity of O(n!), where n is the length of the string. For each permutation, it calculates the number of swaps required to make it a palindrome. Calculating the swaps to make a string a palindrome takes O(n) time in the worst case as we might have to iterate through the string to find misplaced characters and move them. Therefore, the overall time complexity is O(n! * n).
Space Complexity
O(N!)The algorithm explores all possible arrangements of the input string. Generating all permutations requires storing those permutations, resulting in an auxiliary space proportional to the number of permutations which is N! where N is the length of the string. Storing each permutation, which has a length of N, takes O(N) space but there are N! permutations. Thus the dominant space complexity comes from the storage of the permutations, leading to O(N!).

Optimal Solution

Approach

The goal is to rearrange a string into a palindrome with the fewest swaps. The best way to do this is to match characters from the outside in, moving characters only when necessary.

Here's how the algorithm would work step-by-step:

  1. Start with two pointers, one at the beginning of the string and one at the end.
  2. If the characters at both ends are the same, move both pointers inward.
  3. If the characters are different, search from the right pointer towards the left for a character that matches the left pointer's character.
  4. If a matching character is found, swap it step-by-step with the character to its right until it reaches the right pointer's position. Each swap is a move.
  5. After swapping, move both pointers inward.
  6. If no matching character is found for the left pointer's character, it means this character is in the middle of what will become the palindrome. Move it to the middle position of the current substring which will create the least number of swaps.
  7. Repeat these steps until the pointers meet in the middle. The total number of swaps performed is the minimum number of moves to make the string a palindrome.

Code Implementation

def minimum_moves_to_make_palindrome(input_string):
    input_list = list(input_string)
    left_pointer = 0
    right_pointer = len(input_list) - 1
    move_count = 0

    while left_pointer < right_pointer:
        # If chars match, move inward.
        if input_list[left_pointer] == input_list[right_pointer]:
            left_pointer += 1
            right_pointer -= 1
        else:
            index_to_swap = right_pointer
            while index_to_swap > left_pointer and input_list[index_to_swap] != input_list[left_pointer]:
                index_to_swap -= 1

            # No matching char found.
            if index_to_swap == left_pointer:

                move_count += right_pointer - left_pointer
                input_list[left_pointer], input_list[left_pointer + 1] = input_list[left_pointer + 1], input_list[left_pointer]

            # Swap matching char.
            else:
                # Swap chars to make palindrome.
                while index_to_swap < right_pointer:
                    input_list[index_to_swap], input_list[index_to_swap + 1] = input_list[index_to_swap + 1], input_list[index_to_swap]
                    move_count += 1
                    index_to_swap += 1

                left_pointer += 1
                right_pointer -= 1

    return move_count

Big(O) Analysis

Time Complexity
O(n²)The outer loop iterates up to n/2 times, where n is the length of the string, effectively processing each character from the beginning to the middle. Inside the outer loop, the worst-case scenario involves searching for a matching character from the right end towards the current position, which can take up to n steps. Furthermore, if a match is found, swapping can take up to n steps. Thus, the nested loop structure leads to a time complexity of approximately (n/2) * (n + n), which simplifies to n². Therefore, the overall time complexity is O(n²).
Space Complexity
O(1)The algorithm primarily uses two pointers and a few temporary variables for swapping characters. These variables consume a fixed amount of memory, irrespective of the input string's length (N). No auxiliary data structures like lists, arrays, or hash maps are used to store intermediate results. Therefore, the space complexity is constant.

Edge Cases

CaseHow to Handle
Null or empty string inputReturn 0 immediately as an empty string is considered a palindrome.
String with a single characterReturn 0, as a single-character string is already a palindrome.
String with all identical characters (e.g., 'aaaa')Return 0, since the string is already a palindrome.
String where a palindrome can't be formed (e.g., 'abc')Return -1 (or throw an exception) to indicate that a palindrome cannot be formed.
Very long strings (performance implications)Ensure the algorithm's time complexity is optimized to avoid timeouts; aim for O(n^2) or better if possible.
String with mixed case characters (e.g., 'Racecar')Convert the string to lowercase (or uppercase) before processing to ensure case-insensitive comparison.
String with non-alphanumeric characters (e.g., 'A man, a plan, a canal: Panama')Remove non-alphanumeric characters or ignore them during palindrome checking.
String with mostly matching pairs except for one character in the middle (e.g. 'abcdcbea')The algorithm must handle the single unmatched middle character appropriately, shifting it to the center.