Min Adjacent Swaps Palindrome
HardGreedy · Microsoft
Given a string s of lowercase letters, you may repeatedly swap two adjacent characters. Return the minimum number of swaps needed to turn s into a palindrome (a string that reads the same forwards and backwards).
If the letters of s cannot be arranged into any palindrome, return -1.
Example 1
- Input:
- s = "accat"
- Output:
- 2
- Explanation
- Moving the second
aone place right givesaccta(1 swap). Then moving the secondcone place right gives the palindromeactca(2 swaps in total).
Example 2
- Input:
- s = "xyzx"
- Output:
- -1
- Explanation
yandzeach appear once, and a palindrome can have at most one letter with an odd count.
Example 3
- Input:
- s = "abab"
- Output:
- 1
- Explanation
- One swap of the middle two letters gives
abba.
Constraints
1 <= s.length <= 2000scontains only lowercase English letters