adi_isHere's blog

Stuck in a problem
By adi_isHere, history, 18 months 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?
»
18 months ago, # |
  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
  • »
    »
    18 months ago, # ^ |
      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
    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      yeah, i knew most probably my claim must be wrong

      anyways, please tell how to solve the above problem

      → Reply