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.
To solve this problem, we can use dynamic programming. We can define dp[i][j] as the length of the longest valid and palindromic subsequence in the substring starting at index i and ending at index j.
To compute dp[i][j], we can consider the two cases:
Case 1: The i-th and j-th characters are matching parentheses or brackets. In this case, we can add them to the subsequence if the substring between them is also a valid and palindromic subsequence. That is, if dp[i+1][j-1] is not zero, we can add 2 to dp[i][j].
Case 2: The i-th and j-th characters are not matching parentheses or brackets. In this case, we can try to split the substring into two parts and find the longest valid and palindromic subsequence in each part separately. That is, we can try all k in [i, j-1] and compute dp[i][k] and dp[k+1][j], and take the maximum of dp[i][k] + dp[k+1][j].
Finally, the answer to the problem is the maximum dp[i][j] over all i and j such that i <= j.
But in case 2, how would you make sure that the substring is palindromic when you add dp[i][k] and dp[k + 1][j]. For example if dp[i][k] outputs ()() as answer and dp[k + 1][j] outputs [][] as answer, the concatenation of both is not palindromic.
What are the constraints of the problem?
It's more like an algorithmic problem, I was asked this in an interview.
problem link please..
I was asked this during an interview. Unfortunately I am unable to find the problem on leetcode or any platform for now, but if the question is unclear I can clarify.