1
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\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, 2021 at 20:48

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.