Question

2193. Minimum Number of Moves to Make Palindrome

中文文档

Description

You are given a string s consisting only of lowercase English letters.

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

Return _the minimum number of moves needed to make_ s _a palindrome_.

Note that the input will be generated such that s can always be converted to a palindrome.

 

Example 1:

Input: s = "aabb"
Output: 2
Explanation:
We can obtain two palindromes from s, "abba" and "baab". 
- We can obtain "abba" from s in 2 moves: "aabb" -> "abab" -> "abba".
- We can obtain "baab" from s in 2 moves: "aabb" -> "abab" -> "baab".
Thus, the minimum number of moves needed to make s a palindrome is 2.

Example 2:

Input: s = "letelt"
Output: 2
Explanation:
One of the palindromes we can obtain from s in 2 moves is "lettel".
One of the ways we can obtain it is "letelt" -> "letetl" -> "lettel".
Other palindromes such as "tleelt" can also be obtained in 2 moves.
It can be shown that it is not possible to obtain a palindrome in less than 2 moves.

 

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.

Solutions

Solution 1

class Solution:
  def minMovesToMakePalindrome(self, s: str) -> int:
    cs = list(s)
    ans, n = 0, len(s)
    i, j = 0, n - 1
    while i < j:
      even = False
      for k in range(j, i, -1):
        if cs[i] == cs[k]:
          even = True
          while k < j:
            cs[k], cs[k + 1] = cs[k + 1], cs[k]
            k += 1
            ans += 1
          j -= 1
          break
      if not even:
        ans += n // 2 - i
      i += 1
    return ans

class Solution {
  public int minMovesToMakePalindrome(String s) {
    int n = s.length();
    int ans = 0;
    char[] cs = s.toCharArray();
    for (int i = 0, j = n - 1; i < j; ++i) {
      boolean even = false;
      for (int k = j; k != i; --k) {
        if (cs[i] == cs[k]) {
          even = true;
          for (; k < j; ++k) {
            char t = cs[k];
            cs[k] = cs[k + 1];
            cs[k + 1] = t;
            ++ans;
          }
          --j;
          break;
        }
      }
      if (!even) {
        ans += n / 2 - i;
      }
    }
    return ans;
  }
}

class Solution {
public:
  int minMovesToMakePalindrome(string s) {
    int n = s.size();
    int ans = 0;
    for (int i = 0, j = n - 1; i < j; ++i) {
      bool even = false;
      for (int k = j; k != i; --k) {
        if (s[i] == s[k]) {
          even = true;
          for (; k < j; ++k) {
            swap(s[k], s[k + 1]);
            ++ans;
          }
          --j;
          break;
        }
      }
      if (!even) ans += n / 2 - i;
    }
    return ans;
  }
};

func minMovesToMakePalindrome(s string) int {
  cs := []byte(s)
  ans, n := 0, len(s)
  for i, j := 0, n-1; i < j; i++ {
    even := false
    for k := j; k != i; k-- {
      if cs[i] == cs[k] {
        even = true
        for ; k < j; k++ {
          cs[k], cs[k+1] = cs[k+1], cs[k]
          ans++
        }
        j--
        break
      }
    }
    if !even {
      ans += n/2 - i
    }
  }
  return ans
}