Minimum Number Of Moves To Make Palindrome
01 · Problem
You are given a string s of lowercase English letters whose letters can be rearranged into a palindrome (this is guaranteed). In one move you may swap any two adjacent characters of s.
Return the minimum number of moves needed to turn s into a palindrome. Any palindrome is acceptable as the final string; only the number of moves is returned. If s is already a palindrome, return 0.
02 · Examples
s = "abab"
1
One swap turns "abab" into "abba" (swap positions 2 and 3); "baab" is also reachable in one swap.
s = "aabbc"
4
Shift the second "a" to the end with 3 swaps (aabbc -> abbca), then one more swap turns the middle "bbc" into "bcb", giving "abcba". No palindrome is reachable in fewer moves.
s = "racecar"
0
The string is already a palindrome, so 0 moves are needed.
03 · Constraints
- 011 <= s.length <= 2000
- 02s consists only of lowercase English letters
- 03s can always be rearranged into a palindrome
04 · Optimal complexity
- Time
- O(n^2)
- Space
- O(n)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.