Блог пользователя aditya1703

Stuck in a problem
Автор aditya1703, история, 16 месяцев назад, По-английски

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

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
16 месяцев назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      16 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      yeah, i knew most probably my claim must be wrong

      anyways, please tell how to solve the above problem

      → Ответить