Consider two strings \(A = "qpqrr"\) and \(B = "pqprqrp"\). Let \(x\) be the…
2014
Consider two strings \(A = "qpqrr"\) and \(B = "pqprqrp"\). Let \(x\) be the length of the longest common subsequence (not necessarily contiguous) between \(A\) and \(B\) and let \(y\) be the number of such longest common subsequences between \(A\) and \(B\). Then \(x + 10y = \) ______.
Attempted by 140 students.
Show answer & explanation
Correct answer: 34
Compute the longest common subsequence (LCS) length x and the number y of distinct LCSs.
All distinct length-4 subsequences of A = "qpqrr" are: "pqrr", "qqrr", "qprr", "qpqr".
Check which appear in B = "pqprqrp":
"pqrr" appears (for example at positions 1,2,4,6 in B).
"qqrr" does not appear as an ordered subsequence in B.
"qprr" appears (for example at positions 2,3,4,6 in B).
"qpqr" appears (for example at positions 2,3,5,6 in B).
Thus there are three distinct LCS strings of length 4, so x = 4 and y = 3.
Answer: 4 + 10×3 = 34
A video solution is available for this question — log in and enroll to watch it.