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

  • $\begingroup$ cs.stackexchange.com/tags/dynamic-programming/info gives some tips on figuring out the states and their transitions. $\endgroup$ – D.W. Sep 10 '20 at 18:47
  • $\begingroup$ @nope, the question is about the common subsequence. However, Marcelo Fornet's answer only discuss the long balanced subsequence of one string, which is a much simpler problem. Did you accept the answer too soon? $\endgroup$ – John L. Sep 10 '20 at 19:06
  • 1
    $\begingroup$ @JohnL. totally missed one important part of the question. Fortunately creating solution for S and T doesn't change very much, though complexity will be $O(n^3)$ instead of $O(n^2)$ $\endgroup$ – Marcelo Fornet Sep 11 '20 at 3:41
  • $\begingroup$ @JohnL. Yes i accepted the answer too soon,because after seeing his solution for only one string,i found answer to extending it to two strings $\endgroup$ – nope Sep 11 '20 at 5:27

Initially I missed a key part of the question, that is, the subsequence we are looking for must be a common subsequence for two strings $S$ and $T$. I'll keep my initial answer, and will elaborate after that, about how to extend to the case of interest.

One way to detect if a sequence forms a valid balanced parenthesis is to change ( for +1 and ) for -1 and check that the sum of every prefix is non-negative $(P_i \geq 0)$ and the sum of the entire sequence is $0$ ($P_n = 0)$. We define $P_i$ as the balance of the $i$-th prefix.

To compute the largest valid subsequence you can keep track for each prefix $i$ what is the largest valid subsequence of that prefix with a fixed balance $b$: $(Q_i^b)$. The answer to your problem is $Q_n^0$.

Fortunately $Q_i^*$ only depends on the $i$-th character and $Q_{i-1}^*$ so we can use dynamic programming to compute such values. Let's define for the sake of simplicity that for states such that no valid sequences exist the value of $Q_i^b = -\infty$.

The base case for empty prefix $i = 0$.

  • $Q_0^0 = 0$: The largest valid subsequence for the empty prefix is the empty string (size=$0$) which has balance $0$.
  • $Q_0^b = -\infty$: For all balance different than $0$ there is no such string that is subsequence of the empty prefix with balance $b$, so we use $-\infty$.

Let's define transitions to compute each value given that all previous values (with less $i$) are already computed. On each step we either append that character to the end of the subsequence, or we discard that character:

$$Q_i^b = \max(Q_{i - 1}^b, Q_{i - 1}^{b - s[i]} + 1)$$

The first term in the $\max$ expression cover the case that we don't use the last character, so the maximum subsequence with balance $b$ and prefix $i$ is at least as large as the maximum subsequence with balance $b$ and prefix $i - 1$.

The second term in the $\max$ expression cover the case that use the last character, notice that $s[i] = +1$ if there is an open parenthesis ( at position $i$, or $s[i] = -1$ otherwise. Then the new balance will be $b$ if in the previous step the balance was $b - s[i]$, so after adding the $i$-th character it becomes $b$.

We should only compute $Q_i^b$ values for $b \geq 0$, to keep the balance of the sequence always non-negative.

In practice we know the balance won't be larger than $n$ (in fact it won't be larger than $\frac{n}{2}$) so we can compute values of $Q_i^b$ for $0 \leq i \leq n; 0 \leq b \leq n$. Each transition is computed in $O(1)$ so the overall complexity of this solution is $O(n^2)$. Since states $Q_i^*$ only depend on states $Q_{i -1}^*$ we can use only $O(n)$ memory keeping at each moments two rows of the dynamic programming table.

To find a subsequence of two strings $S$ and $T$ we can instead use a dynamic programming state with $3$ dimensions: What is the maximum valid parenthesis sequence with balance $b$ which is a subsequence of prefix of length $i$ from $S$ and prefix of length $j$ from $T$ ($R_{i,j}^b$). The answer is $R_{|S|, |T|}^0$.

The solution is almost the same but transition should be modified to address the new constraint:

$$R_{i, j}^b = \max(R_{i - 1, j}^b, R_{i, j - 1}^b, R_{i - 1, j - 1}^{b- S[i]} \cdot [S[i] == T[j]])$$

The first two terms inside $\max$, handle the case where the best sequence with balance $b$ of prefixes $i$ and $j$ from $S$ and $T$ don't use the last character for both, so at least one of them is not used, and we cover both situations.

The third case is trickier, it handles the case where we do use the last character, but we can only use that character if both character are the same $S[i]$ and $T[j]$, since we most find a common subsequence.

Note about complexity: Now complexity is $O(n^3)$ since that is the number of states and each state is computed in $O(1)$. Again, we can apply a trick to use $O(n^2)$ memory, however it is very tricky to do that and also being able to recover the answer.

In practice: The problem have $n=700$ and time limit $3.5$ seconds. Notice that the number of operations you are doing are roughly $\frac{700^3}{2}=171500000$ basic operations. A modern machine should perform roughly $1e8$ basics operations per second, so this solution should fit in time.

However, to recover the answer you should store for each state, the optimal decision. Notice there are only 3 options, so it fits in 2 bits. It requires $\frac{700^3}{2} \cdot 2$ bits which is $~42MB$. However, if instead of bits, a byte is used to store each decision, the the code will use $\frac{700^3}{2}$ bytes which is $171MB$ and is greater than the limit $128MB$.

  • $\begingroup$ As a extension to my question,how do i recover the sub-sequences.For example S=()()( then sub-sequences which is balanced and maximum length is ()() $\endgroup$ – nope Sep 10 '20 at 18:18
  • $\begingroup$ You should store for each state of the dp $Q_i^b$ what was the optimal decision, either discarding current element of taking. With this table you can recover the subsequence moving backwards always taking the optimal decision. $\endgroup$ – Marcelo Fornet Sep 10 '20 at 18:24
  • $\begingroup$ Thank you for the answer. $\endgroup$ – nope Sep 10 '20 at 18:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.