Why is this code failing for a test case in leetcode problem even that I did reach a better solution than what was expected?

Question

I am solving LeetCode problem 2193. Minimum Number of Moves to Make Palindrome:

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.

I solved the problem with this typescript code:

function minMovesToMakePalindrome(s: string) {
    if (s.length <= 1) return 0;
    if (s[0] === s[s.length - 1]) return minMovesToMakePalindrome(s.slice(1, s.length - 1))
    let leftSwapsCost = s.length;
    let rightSwapsCost = s.length;
    for (let i = 0; i < s.length; i++) {
        if (s[i] === s[0]) {
            // we should swap with the last element
            rightSwapsCost = Math.min(rightSwapsCost, s.length - 1 - i)
        } else if (s[i] === s[s.length - 1]) {
            // we should swap with the first element
            leftSwapsCost = Math.min(leftSwapsCost, i)
        }
    }

    if (leftSwapsCost <= rightSwapsCost) {
        const newString = [s[leftSwapsCost], ...s.slice(1, leftSwapsCost), s[0], ...s.slice(leftSwapsCost + 1)].join('');
        console.log('left: ' + newString + ' cost: ' + leftSwapsCost)
        return leftSwapsCost + minMovesToMakePalindrome(newString.slice(1, s.length - 1))
    } else {
        const newString = [...s.slice(0, s.length - 1 - rightSwapsCost), s[s.length - 1], ...s.slice(s.length - rightSwapsCost, s.length - 1), s[s.length - 1 - rightSwapsCost]].join('');
        console.log('right: ' + newString + ' cost: ' + rightSwapsCost)
        return rightSwapsCost + minMovesToMakePalindrome(newString.slice(1, s.length - 1))
    }
};

Basically I am traversing the array of characters (the string) looking for the index of the items that are equal to the first item then calculate the cost of swapping each one of these with the last item and storing the min of that in rightSwapsCost.

The same thing for the items that are equal to the last item: I calculate the min cost of swapping them with the first item and store it in leftSwapsCost.

Finally, I make the swap which costs the least, and recursively call that function on the new string newString (obtained after swap) that does not contain the first and last element of the original string before the swap.

It passed the initial test cases where S = "aabb" and S = "letelt"

But when I submitted, it didn't accept the answer on the case where S = "eqvvhtcsaaqtqesvvqch". Which is weird because it did make the string palindrome in less moves than what LeetCode was expecting.

I got the following result:

Answer 1

The problem is that you've performed non-adjacent swaps and misevaluated their cost. The challenge asks for the (minimum) number of adjacent swaps. Although it is of course fine to perform non-adjacent swaps and calculate how many adjacent swaps would be needed to achieve the same result, this calculation is wrong.

For instance, for the example input ("eqvvhtcsaaqtqesvvqch") your algorithm picks indices 0 ("e") and 4 ("h") for a swap, and assumes that the cost for this swap is 4, but that is wrong. What would have cost 4 is a rotation that puts that "h" in front of the 4 other characters, as from "eqvvH" to "Heqvv" (I intentionally use uppercase for the letter that is rotated), but not a swap from "EqvvH" to "HqvvE". Yet that is the mutation your code performs. But the cost of such a swap is greater than 4! To get from "EqvvH" to "HqvvE" you would have to do 7 adjacent swaps:

eqvvH
eqvHv
eqHvv
eHqvv
Heqvv
hqEvv
hqvEv
hqvvE

So implement the mutations as rotations, not as non-adjacent swaps:

if (leftSwapsCost <= rightSwapsCost) {
    // Fixed:
    const newString = [s[leftSwapsCost], ...s.slice(0, leftSwapsCost), ...s.slice(leftSwapsCost + 1)].join('');
    console.log('left: ' + newString + ' cost: ' + leftSwapsCost)
    return leftSwapsCost + minMovesToMakePalindrome(newString.slice(1, s.length - 1))
} else {
    // Fixed:
    const newString = [...s.slice(0, s.length - 1 - rightSwapsCost), ...s.slice(s.length - rightSwapsCost), s[s.length - 1 - rightSwapsCost]].join('');
    console.log('right: ' + newString + ' cost: ' + rightSwapsCost)
    return rightSwapsCost + minMovesToMakePalindrome(newString.slice(1, s.length - 1))
}