GATE CS 2014 Set 2 — Question 47
Go beyond PYQs with Success TrackerAI-powered personalised practice and doubt support. Unlimited practice on eligible plans; AI usage limits apply.NAT+2 / -0HardLongest Common SubsequenceDynamic ProgrammingAlgorithms
Algorithms → Dynamic Programming → Longest Common Subsequence
Last updated
Question
Consider two strings and . Let be the length of the longest common subsequence (not necessarily contiguous) between and and let be the number of such longest common subsequences between and . Then ______.
Correct answer
34 to 34
Solution
To find the Longest Common Subsequence (LCS) of and , we can compute the length and then identify the distinct sequences.Step 1: Find the length
Let's determine the LCS length using dynamic programming or inspection.
: length 5
: length 7Common subsequences of length 4:
So, .Step 2: Find the number of distinct LCSs
We identified 3 distinct strings of length 4: "qpqr", "qprr", "pqrr".
Let's check if there are any others. The subsequences of of length 4 are:
So, .Step 3: Calculate result
.
Let's determine the LCS length using dynamic programming or inspection.
: length 5
: length 7Common subsequences of length 4:
1.qpqr: Present in at indices 1,2,3,4. Present in at indices 2,3,5,6.
2.qprr: Present in at indices 1,2,4,5. Present in at indices 2,3,4,6.
3.pqrr: Present in at indices 2,3,4,5. Present in at indices 1,2,4,6.
Can we find length 5? is "qpqrr". Is "qpqrr" a subsequence of ? has only one 'p' after the first 'q' (at index 3) and then 'r', 'q', 'r', 'p'. It does not contain "qpqrr". Thus, max length is 4.So, .Step 2: Find the number of distinct LCSs
We identified 3 distinct strings of length 4: "qpqr", "qprr", "pqrr".
Let's check if there are any others. The subsequences of of length 4 are:
- Drop 1st char (q): "pqrr" (Valid in B)
- Drop 2nd char (p): "qqrr" (In B? has q at 2, 5. r at 4, 6. After q(5), only r(6) exists. Cannot form "qqrr". Invalid)
- Drop 3rd char (q): "qprr" (Valid in B)
- Drop 4th char (r): "qpqr" (Valid in B)
- Drop 5th char (r): "qpqr" (Duplicate)
So, .Step 3: Calculate result
.
Continue learning with Success Tracker
A step still unclear? Work through it with support
Use Success Tracker to ask about the reasoning, then try another GATE CS question to check your understanding.
AI-powered practice· Unlimited practice on eligible plans
- PYQs with solutions
- Attempt available previous-year questions, then compare your reasoning with the worked solution. Coverage varies by stream.
- Practice that adapts
- Choose a topic, work on weaker areas and bookmark questions to revisit. Your attempts feed your progress tracking.
- AI doubt support
- Ask follow-up questions about a step or concept while practising, instead of stopping at the final answer.
Unlimited practice is available on eligible plans. Free practice and AI usage have limits; check the current plan allowances before choosing.
This page stays readable without an account. AI responses can be wrong; check them against the solution and source material.
More questions on Dynamic Programming
2026 Set 1 Q17Consider the following recurrence relations: For all ,…2026 Set 2 Q24Consider the following functions, where is a positive integer.…2026 Set 2 Q25Which of the following can be recurrence relation(s) corresponding to an algorithm with time…2026 Set 2 Q32Consider an array . Suppose the merge sort algorithm is…2026 Set 2 Q37Let be a weighted directed acyclic graph with edges and vertices. Given and a…