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.