Skip to content

2193. Minimum Number of Moves to Make Palindrome 👍

  • Time: $O(n^2)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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 letter.
        ans += i / 2;
      } else {
        s.erase(i, 1);
        ans += i;  // Swap the matched letter to the left.
      }
      s.pop_back();
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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) {
        // s[i] is the middle letter.
        ans += i / 2;
      } else {
        sb.deleteCharAt(i);
        ans += i; // Swap the matched letter to the left.
      }
      sb.deleteCharAt(sb.length() - 1);
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
  def minMovesToMakePalindrome(self, s: str) -> int:
    ans = 0
    chars = list(s)

    while len(chars) > 1:
      # Greedily match the last digit.
      i = chars.index(chars[-1])
      if i == len(chars) - 1:
        # s[i] is the middle letter.
        ans += i // 2
      else:
        chars.pop(i)
        ans += i  # Swap the matched letter to the left.
      chars.pop()

    return ans