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

Palindromic string maximum product interview DP question help

Автор n1e2m3, история, 5 лет назад, По-английски

given a string S. you have to find maximum product of length of two non overlapping palindromic sequence.
here, non overlapping means only indexes are non overlap.

for example,

1)
s = “abcab”
ans = 3*2 = 6
two palindromic sequence are “aca” and “bb”

2 )
s = nriatdoiarn
ans = 5*5 = 25
two palindromic sequences are “nitin” and ( “radar” or “raoar”)

3 )
s = “abcdef”
ans = 1*1 = 1

please share your solution.

Easy Version link : https://stackoverflow.com/questions/53663721/find-the-maximum-product-of-two-non-overlapping-palindromic-subsequences

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

»
5 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

[Deleted]

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Please, someone answer it. This appears to be a very good question to me.

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

stackexchange code is wrong

→ Ответить
»
5 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Wrong idea

→ Ответить
»
5 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

What about the stack exchange answer. It looks correct to me, and is $$$O(n^{2})$$$. Please point out if something is wrong.

So another question is, for $$$A$$$ and $$$B$$$ to be non overlapping subsequences of given string $$$S$$$, what is the exact criteria?

Since $$$A$$$ = $$$S[i_1]$$$,$$$S[i_2]$$$, ... , $$$S[i_{n1}]$$$, and $$$B$$$ = $$$S[j_1]$$$,$$$S[j_2]$$$, ... , $$$S[j_{n2}]$$$ so which of the following do we want: ( assuming $$$i_1$$$ < $$$j_1$$$ )

$$$1)$$$ $$$i_{n1} \lt j_1$$$ ( basically for some string, "abcdefg" if I take $$$A$$$ = "ace" then can I only take letters after 'e' for $$$B$$$? )

OR

$$$2)$$$ $$$i_x != j_y$$$ for each $$$x$$$ in $$$range(1,n1)$$$ ,$$$y$$$ in $$$range(1,n2)$$$. ( no two characters of the same index )

I believe the stack exchange answer is definitely valid, in case of definition $$$1)$$$ of non overlapping subsequences.

UPD: I guess the example $$$2$$$ given in the post, makes it clear that the $$$2)$$$ definition is the one to be used.

→ Ответить
  • »
    »
    5 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

    accbcac its ans is 12 its showing 6, author's concept might be correct,but implementation is wrong. link

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

      How it's answer is 12? It should be 6.

      → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Interesting example. It looks like longest palindromic subsequence dp will fail to give us required answer. For $$$accbcac$$$, lps is length $$$5$$$ ( either $$$accca$$$ or $$$ccbcc$$$ or $$$acbca$$$ ), but we need $$$aba$$$ and $$$cccc$$$ for maximum product.

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

        i know one greedy approach,we know that for sure for palindrome pair both characters should be at maximum distance.but we should insert them in two sets in such way that they should for approximate equal length.

        → Ответить
»
5 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Wrong idea, misread the problem statement.

→ Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Yeah, you need to consider subsequences, not substrings. And even among subsequences, it is not necessary that subsequences will not interleave ( but definitely not intersect ).

    → Ответить