hard Minimum Number of Moves to Make Palindrome

Problem Statement

Given a string s containing only lowercase English letters, return the minimum number of moves needed to make s a palindrome.

In a single move, you can select any two adjacent characters of s and swap them.

Examples

Example 1:

• Input: s = "ababc"
• Expected Output: 3
• Justification: The string "ababc" can be rearranged to form "abcba" with three swaps:
  • Swap the second 'b' and 'c' to get "abacb".
  • Swap the second 'a' and 'c' to get "abcab".
  • Swap the second 'a' and second 'b' to get "abcba".

Example 2:

• Input: s = "aabb"
• Expected Output: 2
• Justification: The string "aabb" can be rearranged to form "abba" with two swaps:
  • Swap the second 'a' and the first 'b' to get "abab".
  • Swap the first 'a' and the first 'b' to get "abba".

Example 3:

• Input: s = "racecar"
• Expected Output: 0
• Justification: The string "racecar" is already a palindrome, so no swaps are necessary.

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

To solve this problem, we need to focus on transforming the given string into a palindrome using the minimum number of swaps. Since the problem guarantees that the string can always be rearranged into a palindrome, our approach involves calculating how far each character is from its desired position in a palindrome configuration and making the necessary swaps.

The strategy is to start from both ends of the string and move toward the center. We identify mismatched characters and swap them in a way that brings the string closer to a palindrome at each step. A Binary Indexed Tree (BIT) is used to efficiently track and update the number of swaps required as we rearrange the characters. The reason this approach is effective is that it allows us to keep track of the order and position of characters efficiently, reducing the complexity of counting and rearranging operations.

Step-by-Step Algorithm

Step 1: Initialize Data Structures

• Initialize an array of lists characterIndices of size 26. This stores positions of each character in s, allowing easy access to all instances of any character.

• Initialize a 2D array indexPointers of size [26][2]. Tracks the leftmost and rightmost unprocessed indices for each character to help in pairing and moving them into correct positions.

• Initialize an array BITree of size s.length(). This acts as a Binary Indexed Tree (BIT) to efficiently calculate the number of swaps needed.

• Initialize a boolean array visited of size s.length(). It tracks which indices have been processed to avoid redundant operations.

Step 2: Populate characterIndices

2.1. Store Indices:

• Iterate through each character in s, and for each character at position i, add i to the corresponding list in characterIndices. Grouping all indices of the same character together allows efficient pairing from both ends of the string.

Step 3: Initialize indexPointers

3.1. Set initial pointers:

• For each character i (from 0 to 25):
  • Set indexPointers[i][0] to 0, pointing to the first occurrence of the character in characterIndices[i].
  • Set indexPointers[i][1] to the last index of characterIndices[i], pointing to the last occurrence.
• These pointers help in finding matching characters from both ends of the string, which will be swapped to form a palindrome.

Step 4: Process the String to Make it a Palindrome

4.1. Iterate with two pointers (left and right):

• Start with right at the last index of the string and move towards left.
• For each position right:
  • If visited[right] is true, skip to the next iteration (this means this position has already been processed).

4.2. Find matching characters:

• Set currentChar to s[right].
• Use indexPointers[currentChar - 'a'] to get the leftmost unprocessed position (leftPointer) and rightmost unprocessed position (rightPointer) of currentChar.
• Pairing characters from both ends towards the center ensures the formation of a palindrome.

4.3. Check if the character is at the center of an odd-length palindrome:

• If leftPointer == rightPointer, it means this character is at the center of an odd-length palindrome.
• In this case, add mid to totalMoves, as the character needs to be moved to the center.
• Handle the special case where a character appears in the middle of an odd-length palindrome.

4.4. Calculate the number of swaps needed:

• If leftPointer != rightPointer, calculate the number of swaps required to move leftPointer to its correct position using:
  • totalMoves += leftPointer - getBITreeValue(leftPointer);
• Explanation:
  • getBITreeValue(leftPointer) returns the cumulative number of swaps that have affected positions up to leftPointer.
  • Subtracting this from leftPointer gives the effective position of the character after accounting for previous swaps.

4.5. Update BITree with the new position:

• Call updateBITree(leftPointer) to update the BIT with the new swap.
• Explanation of updateBITree(index):
  • Increment the value at position index in the BIT.
  • Propagate this increment to all relevant indices in the BIT (using the property index += index & -index).
• Purpose: Update the BIT to reflect the new state after the swap.

4.6. Update pointers and continue:

• Mark visited[leftPointer] and visited[rightPointer] as true.
• Decrease mid to reflect the reduced available space as we move towards the center.
• Purpose: Continue processing until all characters are correctly positioned.

Step 5: Return the Result

5.1. Return totalMoves:

• The final value of totalMoves is the minimum number of adjacent swaps required to transform the string into a palindrome.

Algorithm Walkthrough

Let's walk through the algorithm step-by-step for the string s = "ababc".

1. Initial Setup:

   • String: s = "ababc"
   • Length of s: 5
   • characterIndices: Stores indices of each character:
     • a: [0, 2]
     • b: [1, 3]
     • c: [4]
   • indexPointers: Initialized as:
     • For 'a': [0, 1]
     • For 'b': [0, 1]
     • For 'c': [0, 0]
   • BITree: [0, 0, 0, 0, 0] (empty at the start)
   • visited: [False, False, False, False, False]

2. First Iteration (right = 4):

   • Character: c at index 4.
   • Left Pointer (leftPointer) for c: 4 (only occurrence).
   • Right Pointer (rightPointer) for c: 4 (same as leftPointer).
   • Action: This is the center character of an odd-length palindrome.
     • totalMoves += Math.max(mid, 0). So, totalMoves = 0 + 2 = 2.
   • Updated BITree: [0, 0, 0, 0, 1]

3. Second Iteration (right = 3):

   • Character: b at index 3.
   • Left Pointer (leftPointer) for b: 1.
   • Right Pointer (rightPointer) for b: 3.
   • Update Total Moves: totalMoves = totalMoves + leftPointer - this.getBITreeValue(leftPointer) = 2 + 1 - 0 = 3.
   • Update BITree: Add 1 at index 1. Updated BITree: [0, 1, 0, 1, 1]

4. Third Iteration (right = 2):

   • Character: a at index 2.
   • Left Pointer (leftPointer) for a: 0.
   • Right Pointer (rightPointer) for a: 2.
   • Update Total Moves: totalMoves += 0 - 0 = 3.
   • Update BITree: Add 1 at index 0. Updated BITree: [1, 2, 0, 2, 1]

5. The indices 0 and 1 are already visited.

6. Final Calculation:

   • Total Moves: 3.
   • Output: 3

Code

import java.util.ArrayList;
import java.util.List;

class Solution {

  List<Integer>[] characterIndices; // Array of lists to store indices of each character
  int[][] indexPointers; // Pointers to track positions in character indices
  int[] BITree; // Binary Indexed Tree for efficient calculation of swaps

  public int minMovesToMakePalindrome(String s) {
    characterIndices = new List[26]; // There are 26 lowercase English letters
    indexPointers = new int[26][2]; // Two pointers for each character
    BITree = new int[s.length()]; // BITree array initialization

    // Initialize the list for each character
    for (int i = 0; i < 26; ++i) {
      characterIndices[i] = new ArrayList<>();
    }

    // Fill characterIndices with positions of each character in the string
    for (int i = 0; i < s.length(); ++i) {
      characterIndices[s.charAt(i) - 'a'].add(i);
    }

    // Initialize the pointers for each character
    for (int i = 0; i < 26; ++i) {
      indexPointers[i][0] = 0; // Left pointer starts at 0
      indexPointers[i][1] = characterIndices[i].size() - 1; // Right pointer starts at the last position
    }

    int left = 0;
    int leftPointer, rightPointer;
    char currentChar;
    int totalMoves = 0;
    int currentIdx;
    boolean[] visited = new boolean[s.length()]; // Track visited indices

    int mid = s.length() / 2;

    for (int right = s.length() - 1; right > left; --right) {
      if (visited[right]) continue; // Skip if this index has already been processed

      currentChar = s.charAt(right);

      // Get the positions of the matching characters from both sides
      leftPointer = characterIndices[currentChar - 'a'].get(
        indexPointers[currentChar - 'a'][0]++
      );
      rightPointer = characterIndices[currentChar - 'a'].get(
        indexPointers[currentChar - 'a'][1]--
      );

      visited[leftPointer] = true;
      visited[rightPointer] = true;

      // If leftPointer and rightPointer are the same, it's the center character of an odd-length palindrome
      if (leftPointer == rightPointer) {
        totalMoves += Math.max(mid, 0);
        updateBITree(leftPointer);
        continue;
      }

      // Calculate the number of swaps needed to move the leftPointer to its correct position
      totalMoves += leftPointer - getBITreeValue(leftPointer);
      updateBITree(leftPointer);
      --mid;
    }

    return totalMoves;
  }

  // Update the Binary Indexed Tree with the new index
  private void updateBITree(int index) {
    ++index;

    for (int i = index; i < BITree.length; i += (i & -i)) {
      ++BITree[i];
    }
  }

  // Get the cumulative frequency from the BITree up to the given index
  private int getBITreeValue(int index) {
    index++;
    int cumulativeSum = 0;

    for (int i = index; i > 0; i -= (i & -i)) {
      cumulativeSum += BITree[i];
    }

    return cumulativeSum;
  }

  public static void main(String[] args) {
    Solution solution = new Solution();

    System.out.println(solution.minMovesToMakePalindrome("ababc")); // Expected Output: 3
    System.out.println(solution.minMovesToMakePalindrome("aabb")); // Expected Output: 2
    System.out.println(solution.minMovesToMakePalindrome("racecar")); // Expected Output: 0
  }
}

Complexity Analysis

Time Complexity

• Character Indexing: The code first creates lists for each character in the string, which requires iterating through the string once, making this step where n is the length of the string s.

• BITree Updates and Queries: Each update and query operation on the Binary Indexed Tree (BIT) takes time. In the worst case, the code may perform these operations for each character in the string, making this part of the code .

• Total Time Complexity: Therefore, the overall time complexity is .

Space Complexity

• Character Indexing: The characterIndices array requires space, where n is the length of the string. This is because, in the worst case, every character could be unique, and we'd store all indices.

• BITree: The BITree array also requires space.

• Additional Arrays: The indexPointers and visited arrays require space as well.

• Total Space Complexity: Thus, the space complexity is .