LeetCode-in-Java
2193. Minimum Number of Moves to Make Palindrome
Hard
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 <= 2000sconsists only of lowercase English letters.scan be converted to a palindrome using a finite number of moves.
Solution
public class Solution {
public int minMovesToMakePalindrome(String s) {
int l = 0;
int r = s.length() - 1;
char[] charArray = s.toCharArray();
int output = 0;
while (l < r) {
if (charArray[l] != charArray[r]) {
char prev = charArray[l];
int k = r;
while (charArray[k] != prev) {
k--;
}
// middle element
if (k == l) {
char temp = charArray[l];
charArray[l] = charArray[l + 1];
charArray[l + 1] = temp;
output++;
continue;
}
for (int i = k; i < r; i++) {
char temp = charArray[i];
charArray[i] = charArray[i + 1];
charArray[i + 1] = temp;
output++;
}
}
l++;
r--;
}
return output;
}
}