Swapping characters must be adjacent or any?

nvm

nvm

My solution may will work because I tried: We will take the first string as S. Create a function for finding the minimum number of swapping to make the string(let's call it st1) palindrome Then you should find all characters that has odd occurrence in S with their indeces. Then remove these all characters only once, so remaining character equal to it will be even or 0. Add number of deletions to the cnt_opr. Then take this changed string as st1(as I mentioned in above function) Then add number of swaps to cnt_opr. I think this will work coz I tested it with some examples but cannot code completely :)

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$$$.