993. Palindrome by Swaps
You are given a string s of lowercase letters. In one move you may swap two neighbouring characters. It is guaranteed that the letters of s can be rearranged into a palindrome (at most one letter has an odd count).
Return the minimum number of moves needed to turn s into some palindrome. Any palindrome may be the target; you only need to report the smallest number of adjacent swaps over all of them. The result always fits in a 32-bit integer.
Example 1
- Input:
- s = "abcabc"
- Output:
- 3
- Explanation:
Three adjacent swaps work: abcabc → bacabc → bcaabc → cbaabc, which reads the same backwards, and two swaps are not enough.
Example 2
- Input:
- s = "xyyxz"
- Output:
- 2
- Explanation:
Two swaps work: xyyxz → xyyzx → xyzyx, which is a palindrome, and one swap cannot do it.
Constraints
- 1 ≤ s.length ≤ 40000
- s contains only lowercase English letters
- s can be rearranged into a palindrome
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 800 msC++ 200 msJava 400 msJavaScript 400 msTypeScript 400 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)