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