Palindrome by Adjacent Swaps

Hard

You get a string word of lowercase English letters. In one move you may swap two **adjacent** letters. Return the smallest number of moves that turns the string into a palindrome (it reads the same left to right and right to left). The letters of word are guaranteed to form some palindrome.

Example 1

word="xyxy" → 1

Swap the last two letters: "xyxy" → "xyyx". One swap is enough.

Example 2

word="mamad" → 3

For instance "mamad" → "maamd" → "maadm" → "madam": three swaps, and no fewer will do.

Example 3

word="noon" → 0

Constraints

1 ≤ len(word) ≤ 2000
word consists of lowercase English letters
The letters of word can be arranged into a palindrome

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Binary Indexed Tree Two Pointers String

Similar problems

Mirror Chunk Split Hard Smallest Code by Neighbor Swaps Hard Disjoint Long Palindromes Hard Word Topping Duel Hard Palindrome With One Eraser Stroke Easy

Input

word="xyxy"

Expected

Run checks the first 3 tests in your browser. Submit checks all 70 tests on the server, hidden ones included.