adi_isHere's blog

Stuck in a problem
By adi_isHere, history, 3 years ago, In English

Given a string Str, rearrange Str such that the resultant string T maximizes min (LCS(Str, T) and LCS(Str, reverse(T))).

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

Comments Comments (3)
| Write comment?
»
3 years ago, hide # |
 
Vote: I like it -9 Vote: I do not like it

looks like min (LCS(Str, T) and LCS(Str, reverse(T))) cannot exceed longest palindromic subsequence of Str, hence T=Str should work, i may be wrong tho

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Actually it can exceed that.

    Let $$$str = \text{aabb}$$$, $$$T = \text{abba}$$$. Now, $$$\min(\mathrm{LCS}(\text{aabb}, \text{abba}), \mathrm{LCS}(\text{aabb}, \text{abba})) = \min(3, 3) = 3$$$.

    If you choose $$$T = str$$$, you get $$$\min(\mathrm{LCS}(\text{aabb}, \text{aabb}), \mathrm{LCS}(\text{aabb}, \text{bbaa})) = \min(4, 2) = 2$$$.

    → Reply