2193. Minimum Number of Moves to Make Palindrome

HardGreedyBinary Indexed TreeTwo PointersString
Leetcode Link

Problem Description

You are given a string s that is composed only of lowercase English letters. Your goal is to transform this string into a palindrome using the smallest number of moves possible. A palindrome is a word or phrase that reads the same backward as forward. In each move, you are allowed to select any two adjacent characters in the string and swap them.

The challenge ensures that the given string can always be rearranged into a palindrome, so you don't need to check for the possibility of creating one, only to find the minimum number of moves to do so.

Intuition

The solution approach is based on the principle that, to form a palindrome, the letters must mirror each other from the center of the string outwards. That means characters at the start and end of the string must be the same, then the ones inward from them, and so on, until the middle of the string is reached.

Understanding that, we can work our way inwards from both ends of the string towards the center, making swaps to position each character correctly. At each step, you look for the first occasion of the letter at the i-th position from the start of the string, starting from the j-th position from the end of the string, where j is initially length of the string - 1. When you find a matching letter, it indicates that it needs to be swapped multiple times until it reaches the j-th position. Each swap is counted as one move.

In some cases, there might be a character that does not have a matching pair (an unmatched character) in its immediate search. When such an unmatched situation is found, it means this character must be at the center of the palindrome. Since we know the string can always be a palindrome, there would be at most one such character. For an unmatched character, you need to bring it to the center. This requires a specific number of moves, which is n // 2 - i, considering n is the length of the string.

The process is repeated until i reaches the center of the string, accumulating the number of moves required to place each character in its rightful position for a palindrome.

By following the above approach, the minimum number of moves required to make the string a palindrome can be determined.

Solution Approach

The solution approach for the problem involves a two-pointer technique, iterating from the outermost characters of the string towards the center, and a greedy strategy to make the minimum number of swaps at each step.

Here's a step-by-step breakdown of the algorithm, based on the provided Python implementation:

  1. The string s is converted into a mutable list cs to move characters around easily since strings in Python are immutable.
  2. Two pointers i and j are set up, where i starts at the beginning of the list (0) and j starts at the end (n - 1, where n is the length of the string).
  3. We initiate a counter ans to keep track of the number of moves made.
  4. The while loop begins and continues until i is less than j. Within this loop, we are progressively fixing the characters at the beginning and end of the string while moving towards the center.
  5. Inside the loop, we start an inner loop that goes in reverse from j to i. This reverse loop looks for a character matching cs[i] starting from the j-th position.
  6. If a matching character is found (the even flag is set to True), further nested loops are used to swap the matching character (cs[k]) towards its mirror position at cs[j]. For every swap, the counter ans is incremented.
  7. Once swapping is done, j is decremented, effectively shortening the active part of the list that hasn't been fixed yet.
  8. If no matching character is found (the even flag remains False), it means that the current character cs[i] is unmatched and should be moved to the center. The number of moves is calculated as (n // 2) - i and added to ans.
  9. Pointer i is incremented, and the loop continues until all characters are in the correct position for the palindrome.
  10. After the loop completes, the ans variable contains the total number of moves needed to make s a palindrome.

By using greedy decision-making (choosing the nearest match to swap) and the two-pointer approach, we ensure that we are making swaps that progress towards the desired palindrome with the least number of moves. At the end of the process, the function returns the calculated ans, which is the minimum number of moves needed to transform the string into a palindrome.

💪
Level Up Your
Algo Skills

Example Walkthrough

Let's illustrate the solution approach with a simple example where s = "aabb". Following the steps of the algorithm:

  1. First, we convert the string s to a list cs, so cs = ['a', 'a', 'b', 'b'].
  2. Initialize two pointers: i = 0 and j = 3 (since n = 4, and n - 1 = 3).
  3. Set a counter ans = 0 to keep track of the number of moves made.
  4. The while loop begins with i < j (0 < 3) and will continue until i >= j.
  5. We enter the inner loop starting from j and going towards i. We are looking for the first occurrence of the character cs[i] which is 'a'.
  6. We find that cs[1] equals 'a', thus setting the even flag to True.
  7. Since cs[1] already matches cs[i], no swap is needed, and we do not increment ans.
  8. We now decrease j to 2 and effectively shorten the list to ['a','a','b'].
  9. Pointers are now i = 0 and j = 2. The inner loop will then try to find a match for cs[i] which is 'a' again.
  10. Since cs[2] is 'b' and not a match, and j eventually equals i with no match found, the even flag remains False. This signifies cs[i] is the unmatched character. However, since a does have a match already at cs[1], we know this process completes here without the need for further moves.
  11. Increment i to 1 and as i is now equal to j, the loop ends.

For this simple example, there were 0 moves needed because the string was already in a palindromic order.

Let's take a slightly more complex example: s = "abbaa".

  1. Convert the string s to a list cs, so cs = ['a', 'b', 'b', 'a', 'a'].
  2. Pointers are i = 0, j = 4.
  3. Counter is ans = 0.
  4. Enter the while loop with i < j (0 < 4).
  5. Looking for a match for cs[i] (which is 'a') starting from cs[j].
  6. No swap needed immediately as cs[j] is 'a'.
  7. Decrease j to 3. Move i to 1 since i and j match.
  8. Now look for a match for cs[i] (which is 'b') starting from cs[j].
  9. We find the match immediately at cs[2] which is 'b'.
  10. Decrease j to 2. Since j is now equal to i, no swap is needed.
  11. Increment i to 2. Now i is greater than j, the loop ends.
  12. The unanswered character 'a' in cs[i] now has to be moved to the center.

For this example, one swap is needed to move 'a' from the end to the center, making the string ababa which is a palindrome.

Please note that while these examples are simple, the approach works even with more complex strings and ensures the minimum number of moves because of the greedy two-pointer strategy used.

Python Solution

1class Solution:
2    def min_moves_to_make_palindrome(self, s: str) -> int:
3        # Convert the string into a list for easy manipulation.
4        char_list = list(s)
5        # Initialize the number of moves and the indexes.
6        moves = 0
7        n = len(s)
8        left = 0
9        right = n - 1
10
11        # Iterate until we have checked all characters.
12        while left < right:
13            # Flag to check if we found a matching character.
14            found = False
15
16            # Iterate from right to left starting from the current right index,
17            # looking for a matching character.
18            for k in range(right, left, -1):
19                if char_list[left] == char_list[k]:
20                    # When we find a match, we set found to True.
21                    found = True
22                    # We then move the matched character to its correct position
23                    # by swapping adjacent characters.
24                    while k < right:
25                        char_list[k], char_list[k + 1] = char_list[k + 1], char_list[k]
26                        k += 1
27                        # Increment the moves count for each swap.
28                        moves += 1
29                    # Once we have moved the character to the correct position,
30                    # we decrement the right index.
31                    right -= 1
32                    break
33
34            # If we did not find a matching character, it means
35            # the character needs to be moved to the center for odd length palindrome.
36            if not found:
37                # For this unmatched character, how many moves will it take to reach the center?
38                # It will be half the length of the string minus the current index.
39                moves += (n // 2) - left
40
41            # Move to the next character from the left.
42            left += 1
43
44        # Return the total number of moves required to form a palindrome.
45        return moves
46

Java Solution

1class Solution {
2    public int minMovesToMakePalindrome(String s) {
3        // Length of the given string
4        int length = s.length();
5        // Initialize the count of minimum moves to 0
6        int minimumMoves = 0;
7        // Convert the string to character array for easy manipulation
8        char[] characters = s.toCharArray();
9
10        // We'll use two pointers, starting from the outside of the array moving inwards
11        for (int leftIndex = 0, rightIndex = length - 1; leftIndex < rightIndex; ++leftIndex) {
12            // A variable to check if we have found a matching pair or not
13            boolean pairFound = false;
14
15            for (int searchIndex = rightIndex; searchIndex != leftIndex; --searchIndex) {
16                // Check if the characters match.
17                if (characters[leftIndex] == characters[searchIndex]) {
18                    // If match is found, we set the pairFound status to true
19                    pairFound = true;
20
21                    // Now we need to move the matching character to the right place
22                    for (; searchIndex < rightIndex; ++searchIndex) {
23                        // Swap characters
24                        char temp = characters[searchIndex];
25                        characters[searchIndex] = characters[searchIndex + 1];
26                        characters[searchIndex + 1] = temp;
27
28                        // Incrementing the move counter for each swap
29                        ++minimumMoves;
30                    }
31
32                    // Since we found a pair and moved the character, we can move the right pointer inwards
33                    --rightIndex;
34                    break; // Done with moving the pair, break to outer loop for next character
35                }
36            }
37
38            // If no pair was found for the current character
39            if (!pairFound) {
40                // This means it's the middle character in a palindrome with odd length
41                // We need to move it to the center
42                minimumMoves += length / 2 - leftIndex;
43            }
44        }
45        // Return the minimum number of moves needed to make the string a palindrome
46        return minimumMoves;
47    }
48}
49

C++ Solution

1class Solution {
2public:
3    // Function to find the minimum number of moves to make a string palindrome.
4    int minMovesToMakePalindrome(string str) {
5        int strSize = str.size();   // Length of the string
6        int moves = 0;              // Initialize the number of moves to 0
7      
8        // Use two pointers approach to move characters to form palindrome
9        for (int i = 0, j = strSize - 1; i < j; ++i) {
10            bool foundPair = false; // Flag to check if a character matching the left pointer is found on the right
11          
12            // Loop to find a character from the right that matches with str[i]
13            for (int k = j; k > i; --k) {
14                if (str[i] == str[k]) {
15                    foundPair = true;
16                    // Move the matching character to the correct position on the right
17                    for (; k < j; ++k) {
18                        std::swap(str[k], str[k + 1]); // Swap characters
19                        ++moves; // Increment moves count for each swap
20                    }
21                    --j; // Move the right pointer inwards
22                    break;
23                }
24            }
25          
26            // If no matching character is found, it must be moved to the center of palindrome
27            if (!foundPair) {
28                moves += strSize / 2 - i; // Increment moves by the required positions to reach center
29            }
30        }
31        return moves; // Return total number of moves
32    }
33};
34

Typescript Solution

1// Function to find the minimum number of moves to make a string palindrome.
2function minMovesToMakePalindrome(str: string): number {
3    const strSize: number = str.length;   // Length of the string
4    let moves: number = 0;                // Initialize the number of moves to 0
5
6    // Use two pointers approach to move characters to form palindrome
7    for (let i = 0, j = strSize - 1; i < j; i++) {
8        let foundPair: boolean = false; // Flag to check if a character matching the left pointer is found on the right
9
10        // Loop to find a character from the right that matches with str.charAt(i)
11        for (let k = j; k > i; k--) {
12            if (str.charAt(i) === str.charAt(k)) {
13                foundPair = true;
14                // Move the matching character to the correct position on the right
15                for (; k < j; k++) {
16                    str = swapCharacters(str, k, k + 1); // Swap characters
17                    moves++; // Increment moves count for each swap
18                }
19                j--; // Move the right pointer inwards
20                break;
21            }
22        }
23      
24        // If no matching character is found, it must be moved to the center of the palindrome
25        if (!foundPair) {
26            moves += Math.floor(strSize / 2) - i; // Increment moves by the required positions to reach center
27        }
28    }
29    return moves; // Return total number of moves
30}
31
32// Helper function to swap characters in a string and return the new string
33function swapCharacters(s: string, i: number, j: number): string {
34    const charArray: string[] = [...s]; // Convert string to array for swapping
35    const temp: string = charArray[i];
36    charArray[i] = charArray[j];
37    charArray[j] = temp;
38    return charArray.join(''); // Convert array back to string and return
39}
40

Time and Space Complexity

The given Python code defines a method minMovesToMakePalindrome that calculates the minimum number of adjacent swaps required to make the input string a palindrome.

Time Complexity:

The time complexity of the code is governed by the two nested loops (the while and the inner for loop) that traverse the characters of the string. The outer while loop runs for approximately n/2 iterations, where n is the length of the string (since i starts from 0 and j starts from n - 1 and they move towards the center).

Inside the outer loop, the for loop searches for a matching character from the end of the substring to the current position of i. In the worst-case scenario, this can lead to about n comparisons for the first iteration of the outer loop, then n-2 for the next, and so on. This pattern of comparisons forms a series that can be approximated to n/2 computations on average per outer loop iteration.

Furthermore, the swapping operations within the while loop (inside the inner for if a match is found) have a potential to run up to n times in worst-case scenarios. This adds up to another series of operations contributing to the time complexity.

Thus, the total time complexity is the summation of these two series of operations, which can be estimated with the arithmetic series summation formula. The time complexity approximates to O(n^2).

Space Complexity:

The space complexity is determined by the additional space required by the algorithm aside from the input string. Here, the input string is converted to a list cs, which utilizes O(n) space. The rest of the variables (ans, n, i, j, even, and k) use constant space.

Therefore, the total space complexity of the algorithm is O(n), as the space used by the list cs is the only space that grows proportionally with the input size.

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫