Rating changes for the last round are temporarily rolled back. They will be returned soon. ×

444iq's blog

By 444iq, history, 5 months ago, In English,

How to approach this problem. My approach was to find the prfix from 0 to i and suffix from n — 1 to i + 1. concatenate both for a new string and find longest palindromic subsequence for the current string. But it gave wrong answer and later I realized that my approach will not work always.

Any other approach for this problem. The tag was dp for the problem.

Thanks.

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

I think it can be easily solved in O(|S|^3). Break S into two parts and find longest common subsequence b/w two parts. Answer will be maximum among all cases.

There are |S| ways to break and LCS can be solved in |S|^2.

Giving a complexity of n^3.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    OOps. thanks a lot. I over complicated the problem. yes, it will work. Thanks for help.