Need help with a DP problem

Правка en1, от 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.

Теги dynamic programming, dp, subsequence problem, subsequence

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский Krutik-patel 2023-03-22 22:56:54 876 Initial revision (published)