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