Leetcode

Minimum Number of Moves to Make Palindrome

  • Time:O(n^2)
  • Space:O(n)

C++

class Solution {
 public:
  int minMovesToMakePalindrome(string s) {
    int ans = 0;

    while (s.length() > 1) {
      // greedily match the last digit
      const int i = s.find(s.back());
      if (i == s.length() - 1) {
        // s[i] is the middle char
        ans += i / 2;
      } else {
        s.erase(i, 1);
        ans += i;  // swapped the matches char to the left
      }
      s.pop_back();
    }

    return ans;
  }
};

JAVA

class Solution {
  public int minMovesToMakePalindrome(String s) {
    int ans = 0;
    StringBuilder sb = new StringBuilder(s);

    while (sb.length() > 1) {
      // greedily match the last digit
      final int i = sb.indexOf(sb.substring(sb.length() - 1));
      if (i == sb.length() - 1) {
        // sb.charAt(i) is the middle char
        ans += i / 2;
      } else {
        sb.deleteCharAt(i);
        ans += i; // swapped the matches char to the left
      }
      sb.deleteCharAt(sb.length() - 1);
    }

    return ans;
  }
}

Python

class Solution:
  def minMovesToMakePalindrome(self, s: str) -> int:
    ans = 0
    A = list(s)

    while len(A) > 1:
      # greedily match the last digit
      i = A.index(A[-1])
      if i == len(A) - 1:
        # s[i] is the middle char
        ans += i // 2
      else:
        A.pop(i)
        ans += i  # swapped the matches to the left
      A.pop()

    return ans