# 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

• 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;
}
};

• 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


• 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
}