Sunnatov's blog

Make a string a palindrome in the minimum number of operations
By Sunnatov, 2 years ago, translation, In English

Hello everyone. Recently I saw an interesting problem and could not solve it. I think you can help :)

Given a string $$$ s $$$. In one operation, you can delete a character or swap adjacent characters. Find minimum number of operations to make a string palindrome.

$$$1 \leq |s| \leq 10^6$$$

  • Vote: I like it
  • +16
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
2 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Swapping characters must be adjacent or any?

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply