# Longest substring creating palindromic substring in other string

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?

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