Question 47

Given Strings:

Finding LCS Length $x$:
Constructing the DP table for lengths:

• Subsequences of length 4:
  • Check qprr: in $A$, indices are $0, 2, 3, 4$ (q, q, r, r $\to$ with matching q at 0, p at 1, r at 3, r at 4); in $B$, q at 1, p at 2, r at 3, r at 5. Match found!
  • Check qpqr: in $A$, q(0), p(1), q(2), r(3); in $B$, q(1), p(2), q(4), r(5). Match found!
  • Check pqrr: in $A$, p(1), q(2), r(3), r(4); in $B$, p(0), q(1), r(3), r(5). Match found!
• Can we form length 5? The only length-5 subsequence of $A$ is $A$ itself (qpqrr). Looking for qpqrr in $B$: first q is at index 1, next p at index 2, next q at index 4, next r at index 5. But $B$ has no second r after index 5! So length 5 is impossible.
• Thus, maximum length $x = 4$.

Enumerating Distinct LCS of Length 4 ($y$):
The 4-character subsequences of $A$ are:

• Dropping index 0 (q): pqrr (present in $B$)
• Dropping index 1 (p): qqrr (not in $B$, since $B$ has only one q before r)
• Dropping index 2 (q): qprr (present in $B$)
• Dropping index 3 (r): qpqr (present in $B$)
• Dropping index 4 (r): qpqr (duplicate)
  Thus, there are exactly 3 distinct LCS strings: {"qprr", "qpqr", "pqrr"}.

Computing $x + 10y$: