GATE CS 2014 Set 2 Q37 — Algorithm Design: Dynamic Programming

To find the length ($x$) and the number ($y$) of the longest common subsequences (LCS) between $A = \text{"qpqrr"}$ and $B = \text{"pqprqrp"}$:

Since the length of $A$ is $5$, any subsequence of $A$ of length $4$ is obtained by deleting exactly one character from $A$. Let's list all unique subsequences of $A$ of length $4$:

• Delete $1^{\text{st}}$ character ($q$): "pqrr"
• Delete $2^{\text{nd}}$ character ($p$): "qqrr"
• Delete $3^{\text{rd}}$ character ($q$): "qprr"
• Delete $4^{\text{th}}$ or $5^{\text{th}}$ character ($r$): "qpqr"

Now, we check which of these are also subsequences of $B = \text{"pqprqrp"}$:

1. "pqrr": Yes, matched at indices $1, 2, 4, 6$ of $B$ ($\underline{p}\underline{q}p\underline{r}q\underline{r}p$).
2. "qqrr": No, because matching two $q$'s (at indices $2$ and $5$) leaves only one $r$ (at index $6$) before the end of $B$.
3. "qprr": Yes, matched at indices $2, 3, 4, 6$ of $B$ ($p\underline{q}\underline{p}\underline{r}q\underline{r}p$).
4. "qpqr": Yes, matched at indices $2, 3, 5, 6$ of $B$ ($p\underline{q}\underline{p}r\underline{q}\underline{r}p$).

The only subsequence of length $5$ is $A$ itself, which is not a subsequence of $B$. Thus, the length of the LCS is $x = 4$, and the number of distinct longest common subsequences is $y = 3$ (which are "pqrr", "qprr", and "qpqr").

Calculating the required value: