2193. Minimum Number of Moves to Make Palindrome - Detailed Explanation

Problem Statement

Given a string s, you need to determine the minimum number of adjacent swaps required to transform s into a palindrome. If it is impossible to form a palindrome from s, return -1. In one move, you can swap any two adjacent characters.

For a string to be rearranged into a palindrome, at most one character may appear an odd number of times; all other characters must appear an even number of times.

Example 1

• Input: s = "mamad"
• Output: 3
• Explanation:
  One optimal sequence of swaps is:
  1. Swap the characters at positions 3 and 4: "mamad" → "mamda"
  2. Swap the characters at positions 2 and 3: "mamda" → "madma"
  3. Swap the characters at positions 3 and 4: "madma" → "madam"
     "madam" is a palindrome.

Example 2

• Input: s = "asflkj"
• Output: -1
• Explanation:
  It is impossible to rearrange "asflkj" into any palindrome since more than one character appears an odd number of times.

Example 3

• Input: s = "aabb"
• Output: 2
• Explanation:
  One way to form a palindrome is to swap the middle two characters: "aabb" → "abab" and then "abab" → "abba".
  (Other valid palindromes such as "baab" might be formed with a similar number of moves.)

Hints

1. Palindrome Feasibility Check:
   Before attempting to count moves, count the frequency of each character. If more than one character has an odd frequency, forming a palindrome is impossible.

2. Greedy Two-Pointer Approach:
   Use two pointers, one starting from the beginning (left) and one from the end (right) of the string. Compare the characters:

   • If they are the same, move both pointers inward.
   • If they differ, search for a matching character from the right side (for the left pointer) or from the left side (for the right pointer). The number of swaps needed is determined by how many positions the matching character needs to be moved.

Approach: Greedy Two-Pointer Method with Adjacent Swaps

Explanation

The idea is to iteratively pair matching characters from the two ends of the string until the entire string becomes a palindrome.

1. Check Feasibility:
   Count the frequency of each character. If more than one character occurs an odd number of times, return -1 immediately.

2. Initialize Two Pointers:
   Set pointer i at the beginning and pointer j at the end of the string.

3. Iterate and Swap:

   • If s[i] is equal to s[j], these characters are already paired correctly, so move both pointers inward.
   • If they do not match, search for a matching character for s[i] by moving a pointer k from j towards i.
     • If a match is found (i.e., s[k] == s[i]), perform adjacent swaps to bring the matching character from position k to position j. The number of swaps will be (j - k). After swapping, move both i and j inward.
     • If no match is found (which means s[i] is the unique middle character in an odd-length palindrome), swap s[i] with s[i+1] (one adjacent swap) and increment the move count. Do not move pointer j in this case; instead, try to find a matching pair again.

4. Continue Until Completion:
   Repeat the above steps until the pointers meet or cross. The accumulated count of swaps is the answer.

Step-by-Step Walkthrough

Consider the input s = "mamad":

1. Initial String:
   s = "mamad"
   Set i = 0 and j = 4.

2. First Comparison:

   • Compare s[0] = 'm' with s[4] = 'd'.
   • They do not match. Search for a matching 'm' starting from index j moving leftwards.
   • Found a match at index k = 2 (s[2] = 'm').
   • Swap adjacent characters to move the 'm' at index 2 to index 4:
     • Swap positions 2 and 3: "mamad" → "maamd" (1 move)
     • Swap positions 3 and 4: "maamd" → "maadm" (1 move)
   • Now, s[0] ('m') matches s[4] ('m'). Move i to 1 and j to 3.
   • Total moves so far: 2.

3. Second Comparison:

   • Now, compare s[1] = 'a' with s[3] = 'd'.
   • They do not match. Search for a matching 'a' starting from index j moving leftwards.
   • No match is found between indices 1 and 3 because s[2] = 'a' is not present; instead, s[2] might be 'a' in some cases.
     In our string "maadm", check positions:
     • s[1] = 'a', s[3] = 'd'.
     • Look for 'a' from index 3 to index 1:
       • At index 3: 'd' ≠ 'a'
       • At index 2: 'a' equals 'a' (match found at k = 2).
   • Swap adjacent characters to move the 'a' from index 2 to index 3:
     • Swap positions 2 and 3: "maadm" → "madam" (1 move)
   • Now, s[1] ('a') matches s[3] ('a'). Move i to 2 and j to 2.
   • Total moves so far: 2 (from first comparison) + 1 = 3.

4. Termination:

   • When i equals j (both pointing at the middle character 'd'), the process ends.
   • The total number of moves required is 3.

Complexity Analysis

• Time Complexity:
  In the worst case, for every character pair you might need to shift a character from nearly the entire length of the string. This leads to a worst-case complexity of O(n²), where n is the length of the string.

• Space Complexity:
  The algorithm works in-place (or on a mutable copy of the string), so the extra space used is O(n) if you convert the string to a list of characters for swapping; otherwise, it is O(1) additional space.

Python Code