Need help with a DP problem

Revision en1, by Krutik-patel, 2023-03-22 22:56:54

Recently, I came across this problem and I am unable to figure out the solution.

The problem gives you a string which is made up of '(', ')', '[' and ']'. You need to find the longest sub-sequence which is both palindromic and also valid (balanced string). A string is palindromic if the reverse of the string (the open and close brackets and parentheses are interchanged while taking the reverse) is same as the string. For example, ()() is palindromic, but ())( is not palindromic (a string as seen in a mirror if it's same, then the string is palindromic).

I know how to solve for individual parts (palindromic and balanced separately), but am not able to figure out how to approach this problem when I have to find a sub-sequence which is both palindromic and balanced. Any help on this problem is greatly appreciated. Thanks in advance.

Tags dynamic programming, dp, subsequence problem, subsequence

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Krutik-patel 2023-03-22 22:56:54 876 Initial revision (published)