Given two strings $s, t$, I would liketo find a maximal subsequence of $t$ (denoted as $t'$), such that the concatenation of $t'$ with its reverse ($t'_R$), is a palindromic substring of $s$.

I thought to use dynamic programing to solve this question, but I'm not sure how to use it and how to define the recurrence function and what each cell in the DP should represent.

How can it be solved efficiently?

  • $\begingroup$ Yes, it can be solved in $O(n)$ time assuming the size of alphabet is a constant. I will write an answer. $\endgroup$
    – John L.
    Oct 19 '21 at 20:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.