2193. Minimum Number of Moves to Make Palindrome
https://leetcode.com/problems/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 <= 2000sconsists only of lowercase English letters.scan be converted to a palindrome using a finite number of moves.
---
Time - O(n ^ 2)
Space - O(n)
---
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public int minMovesToMakePalindrome(String s) { | |
| int ans = 0; | |
| StringBuilder sb = new StringBuilder(s); | |
| while (sb.length() > 0) { | |
| char last = sb.charAt(sb.length() - 1); | |
| int index = sb.toString().indexOf(last); | |
| // if last character is unique, it should move to middle | |
| if (index == sb.length() - 1) { | |
| ans += sb.length() / 2; | |
| } else { | |
| // swap to first index | |
| ans += index; | |
| // remove char at last position | |
| sb.deleteCharAt(index); | |
| } | |
| // last char is resolved | |
| sb.setLength(sb.length() - 1); | |
| } | |
| return ans; | |
| } | |
| } |
