Palindromic string maximum product interview DP question help

help
, , , , ,
1

given a string S. you have to find maximum product of length of two non overlapping palindromic sequence.
here, non overlapping means only indexes are non overlap.

for example,
1)
s = “abcab”
ans = 3*2 = 6
two palindromic sequence are “aca” and “bb”

2 )
s = nriatdoiarn
ans = 5*5 = 25
two palindromic sequences are “nitin” and ( “radar” or “raoar”)

3 )
s = “abcdef”
ans = 1*1 = 1

please share your solution.

Easy Version link : java - Find the maximum product of two non overlapping palindromic subsequences - Stack Overflow

2 Likes
2

Hi, i am not absolutely sure but i guess we could work greedily here.given stackexchange solution gives wrong answer on the test case :accbcac it must be 12, but it is showing 6.
so,according to me, again not so sure, for palindromic subsequence,take rightmost matching character for each character,and put under two sets, which would provide nearly equal length.and then find longest palindromic subsequence of both.
note:you have to optimise it.