algorithms – Balanced sub-sequence – Computer Science Stack Exchange


Consider two strings $S$ and $T$ of length $n$.Here both the strings $S$ and $T$ consists of only
$”(“$ and $”)”$ that is made of parenthesis. I need to find a string $w$ which is balanced parenthesis and it should be sub-sequences of both $S$ and $T$ among all those strings $w$ i need the maximum length strings.

This problem is clearly a dynamic programming problem,but i am having hard time in finding states and also their transitions .Could anyone help me.

P.S – Problem E ,but it is in Russian