Swapping characters must be adjacent or any?

nvm

nvm

The version without swaps is known to be quadratically hard (Longest Palindromic Subsequence). It’s unlikely that this version is not. I’ll describe an $$$O(n^2)$$$ algorithm for this problem anyways, as I still find it interesting.

First of all, it’s always optimal to perform deletions first, and then swaps. Second of all, the key observation is that you never swap some position twice (it’s just as good to delete it and its ‘mate’). So, after deletion, you can restrict the swaps to be just some matching of adjacent positions. Moreover, two positions that are ‘mate’ in the final string should not both be swapped (it’s just as good to delete them, again). So swapping is useful only when fixing two mates, i.e. $$$…ab…ab…$$$.

Then, we can compute the classical $$$dp(l, r)$$$ equal to the minimum number of ops for range $$$s[l..r]$$$. We’ll also keep two binary masks $$$m_l$$$ and $$$m_r$$$, the characters that we can consider for a swap that appear before the first match and after the last match in some solution of cost $$$dp(l, r)$$$.

Then, if $$$s_l = s_r$$$, we have $$$dp(l, r) = dp(l+1, r-1)$$$ and $$$m_l(l, r) = m_r(l, r) = 0$$$, otherwise $$$dp(l, r) = \max(dp(l+1, r) + z_l, dp(l, r-1) + z_r)$$$, where $$$z_l = 1$$$ if $$$m_r(l+1, r)$$$ contains $$$s_l$$$ and $$$0$$$ otherwise (similarly for $$$z_r$$$).

Some more care is required to handle updating $$$m_l(l, r)$$$ and $$$m_r(l, r)$$$ in the cases where $$$z_l$$$ or $$$z_r$$$ are $$$0$$$.