LCS appears across GATE, UGC NET and placement rounds. Nine of these 12 questions are previous-year papers, running from GATE 2009 to UGC NET June 2025; the other three drill the definitions those papers assume. Attempt each one before reading its solution.
Every previous-year question below links to its full solution page. The same LCS material is taught end to end in GATE Guidance by Sanchit Sir and Coding for Placements.
LCS basics: supersequences, cost and length (Q1 to Q3)
A subsequence preserves order, not contiguity; a substring requires both. LCS finds the longest sequence shared by two strings. The same prefix pairs come back again and again in the recursion, so caching them in an O(mn) table is exactly the overlapping-subproblem idea from Dynamic Programming Explained.
Q1. LCS and SCS
The longest common subsequence problem and the shortest common supersequence problem are:
(a) Totally unrelated
(b) The same problem
(c) Complementary to each other
(d) Variants of the knapsack problem
Answer: (c) Complementary to each other. For lengths m and n:
length(SCS) = m + n - length(LCS)
One DP table gives both lengths. That is complementary; knapsack has capacity and weights.
Q2. DP complexity
What is the time complexity of the longest common subsequence problem solved using dynamic programming?
(a) O(n)
(b) O(n²)
(c) O(n³)
(d) O(log n)
Answer: (b) O(n²). Two length-n strings produce (n+1)² constant-work cells, hence O(n²). For lengths m and n, it is O(mn).
Q3. LCS length
For a string X = "AGGTAB" and Y = "GXTXAYB", what is the length of the longest common subsequence (LCS)?
(a) 4
(b) 5
(c) 6
(d) 3
Answer: (a) 4. GTAB uses X positions 2, 4, 5, 6 and Y positions 1, 3, 5, 7. Length 5 is impossible because G, T, A and B each supply at most one shared occurrence.
Computing the length with the DP table: Q4 and Q5
L[i][j] covers prefixes X[1..i] and Y[1..j]. Set row 0 and column 0 to zero. Match takes diagonal +1; mismatch takes max(upper, left).
Q4. UGC NET December 2018
Consider two sequences X and Y: X = <0, 1, 2, 1, 3, 0, 1>, Y = <1, 3, 2, 0, 1, 0>. The length of the longest common subsequence between X and Y is:
(a) 2
(b) 3
(c) 4
(d) 5
Answer: (c) 4. Filling the table gives:
X \ Y | ∅ | 1 | 3 | 2 | 0 | 1 | 0 |
|---|---|---|---|---|---|---|---|
∅ | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
1 | 0 | 1 | 1 | 1 | 1 | 2 | 2 |
2 | 0 | 1 | 1 | 2 | 2 | 2 | 2 |
1 | 0 | 1 | 1 | 2 | 2 | 3 | 3 |
3 | 0 | 1 | 2 | 2 | 2 | 3 | 3 |
0 | 0 | 1 | 2 | 2 | 3 | 3 | 4 |
1 | 0 | 1 | 2 | 2 | 3 | 4 | 4 |
L[7][6] = 4. Traceback gives <1, 2, 0, 1> at X positions 2, 3, 6, 7 and Y positions 1, 3, 4, 5. <1, 3, 0, 1> also works: one length, several sequences. Solution: UGC NET December 2018.
Q5. UGC NET June 2025
The longest common subsequence of {1,2,3,2,4,1,2} and {2,4,3,1,2,1} is:
(a) 2,1,2,3
(b) 1,3,2,1
(c) 2,3,2,1
(d) 2,3,1,2,1
Answer: (c) 2,3,2,1. The DP corner is 4, so the answer has length 4. Option (c) uses positions 2, 3, 4, 6 in the first sequence and 1, 3, 5, 6 in the second. Options (a), (b) and (d) respectively need a later 3, 3 and 1 where none exists, so none of them is common to both sequences. Check a candidate against both sequences before trusting its length. Solution: UGC NET June 2025.
When the exam wants the subsequence itself: Q6 and Q7
Trace back from the bottom-right: diagonal on a match, towards the larger neighbour otherwise.
Q6. UGC NET November 2017
Consider the following two sequences: X = <B, C, D, C, A, B, C> and Y = <C, A, D, B, C, B>. The length of the longest common subsequence of X and Y is:
(a) 5 (b) 3 (c) 4 (d) 2
Answer: (c) 4. <C, A, B, C> uses X positions 2, 5, 6, 7 and Y positions 1, 2, 4, 5; <C, D, B, C> also works. The DP corner is 4. Solution: UGC NET November 2017.
Q7. UGC NET December 2015
Given two sequences X and Y: X = <a,b,c,b,d,a,b>, Y = <b,d,c,a,b,a>. The longest common subsequence of X and Y is:
(a) <b,c,a> (b) <c,a,b> (c) <b,c,a,a> (d) <b,c,b,a>
Answer: (d) <b,c,b,a>. It uses X positions 2, 3, 4, 6 and Y positions 1, 3, 5, 6. Options (a) and (b) are shorter; (c) needs a later second a in X. Solution: UGC NET December 2015.
The LCS recurrence and its fill order: GATE 2009 (Q8 and Q9)
GATE 2009 linked the recurrence to its table-filling order.
Q8. GATE 2009 recurrence
A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences X[m] and Y[n] of lengths m and n respectively, with indexes of X and Y starting from 0. We wish to find the length of the longest common sub-sequence (LCS) of X[m] and Y[n] as l(m,n), where an incomplete recursive definition for the function l(i,j) to compute the length of the LCS of X[m] and Y[n] is given below:
l(i,j) = 0, if either i=0 or j=0
= expr1, if i,j > 0 and X[i-1] = Y[j-1]
= expr2, if i,j > 0 and X[i-1] != Y[j-1](a) expr1 ≡ l(i-1, j) + 1
(b) expr1 ≡ l(i, j-1)
(c) expr2 ≡ max(l(i-1, j), l(i, j-1))
(d) expr2 ≡ max(l(i-1,j-1), l(i,j))
Answer: (c) expr2 ≡ max(l(i-1, j), l(i, j-1)). A match needs l(i-1,j-1)+1, eliminating (a) and (b). A mismatch drops either final element and takes the maximum, as (c) states. Option (d) is circular. Solution: GATE 2009 recurrence.
Q9. GATE 2009 fill order
A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences X[m] and Y[n] of lengths m and n, respectively, with indexes of X and Y starting from 0. Consider the data given in the previous question. The values of l(i, j) could be obtained by dynamic programming based on the correct recursive definition of l(i, j) of the form given above, using an array L[M, N], where M = m+1 and N = n+1, such that L[i, j] = l(i, j). Which one of the following statements would be TRUE regarding the dynamic programming solution for the recursive definition of l(i, j)?
(a) All elements L should be initialized to 0 for the values of l(i,j) to be properly computed
(b) The values of l(i,j) may be computed in a row major order or column major order of L(M,N)
(c) The values of l(i,j) cannot be computed in either row major order or column major order of L(M,N)
(d) L[p,q] needs to be computed before L[r,s] if either p < r or q < s.
Answer: (b) The values of l(i,j) may be computed in a row major order or column major order of L(M,N). A cell reads only its diagonal, upper and left neighbours, and all three are already filled in either sweep. Option (a) overstates the setup: only row 0 and column 0 need zeroes. Option (d) uses the wrong connective. A cell waits on L[p,q] when p is at most r and q is at most s, not when just one of the two is smaller, so L[1,0] can safely be filled before L[0,5]. Solution: GATE 2009 fill order.
Counting the LCSs: the GATE 2014 NAT, Q10
A numerical-answer-type question takes a typed value, with no options to eliminate, as the GATE question types primer sets out. Here the value hides a trap: count distinct subsequences, not traceback paths.
Q10. GATE 2014 Set 2
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 = ______.
Answer: 34. The DP corner gives x = 4. The distinct length-4 common subsequences are:
qpqr: A positions 1, 2, 3, 4; B positions 2, 3, 5, 6.
qprr: A positions 1, 2, 4, 5; B positions 2, 3, 4, 6.
pqrr: A positions 2, 3, 4, 5; B positions 1, 2, 4, 6.
So y = 3 and x + 10y = 4 + 30 = 34. Count distinct strings, not paths. Solution: GATE 2014 Set 2 NAT.
Harder variants: weighted and palindromic subsequences
These variants require a fresh case split, not the LCS recurrence.
Q11. GATE 2010 weighted subsequence
The weight of a sequence a0, a1, ..., a(n-1) of real numbers is defined as a0 + a1/2 + ... + a(n-1)/2^(n-1). A subsequence of a sequence is obtained by deleting some elements from the sequence, keeping the order of the remaining elements the same. Let X denote the maximum possible weight of a subsequence of a0, a1, ..., a(n-1) and Y the maximum possible weight of a subsequence of a1, a2, ..., a(n-1). Then X is equal to:
(a) max(Y, a0 + Y) (b) max(Y, a0 + Y/2) (c) max(Y, a0 + 2Y) (d) a0 + Y/2
Answer: (b) max(Y, a0 + Y/2). Skipping a0 gives Y. Taking it shifts every tail term right, halving the best tail weight. Thus X = max(Y, a0 + Y/2). Option (a) misses the shift. Solution: GATE 2010 weighted subsequence.
Q12. UGC NET December 2023 palindrome trap
Which of the following is not a palindromic subsequence of the string "ababcdabba" ?
(a) abcba (b) abba (c) abbbba (d) adba
Answer: (d) adba. adba occurs at 1, 6, 8, 10 but reverses to abda. Valid palindromes are abcba at 1, 2, 5, 8, 10; abba at 1, 2, 9, 10; abbbba at 1, 2, 4, 8, 9, 10. Test palindromicity first. Solution: UGC NET December 2023.
The short version and your next step
A subsequence preserves order, not contiguity.
LCS is O(mn): match takes diagonal +1; mismatch takes max.
Traceback finds a sequence; several LCSs may share one length.
length(SCS) = m + n - length(LCS).Weighted and palindrome variants need new case splits.
The linked learn pages carry about 25 LCS and subsequence questions in all, so roughly 16 are still waiting beyond the nine solved here. Work those unaided, then browse GATE CS preparation options for your next topic.
