Consider two sequences X and Y: X = ( 0, 1, 2, 1, 3, 0, 1 ) Y = (1, 3, 2, 0,…
2026
Consider two sequences X and Y:
X = ( 0, 1, 2, 1, 3, 0, 1 )
Y = (1, 3, 2, 0, 1, 0 )
What is the length of the longest common subsequence between X and Y?
- A.
3
- B.
5
- C.
2
- D.
4
Attempted by 54 students.
Show answer & explanation
Correct answer: D
To find the length of the longest common subsequence (LCS) between X = (0, 1, 2, 1, 3, 0, 1) and Y = (1, 3, 2, 0, 1, 0), we can use dynamic programming or trace common elements maintaining order. One valid common subsequence is (1, 2, 0, 1). In X, these appear at indices 1, 2, 5, 6. In Y, they appear at indices 0, 2, 3, 4. Since the order is preserved in both sequences and no longer common subsequence exists due to ordering constraints, the maximum length is 4.