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 <= 2000sconsists only of lowercase English letters.scan be converted to a palindrome using a finite number of moves.
Solutions
Solution 1
PythonJavaC++Go
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(code-box)
