Longest Common Subsequence (LCS) Implementation

Learn core concepts, essential formulas, and attempt practice questions designed on the latest TCS NQT testing patterns.

Key Concepts & Formulas

1LCS: Longest sequence present in both strings in the same order (not necessarily contiguous).
2DP state: dp[i][j] = dp[i-1][j-1] + 1 if char matches, else max(dp[i-1][j], dp[i][j-1]).

Practice Question 1

Find length of LCS of 'ABCD' and 'ACDF':

A) 3

B) 4

C) 2

D) 1

Correct Answer: A) 3

Step-by-step Solution: The common subsequence is 'ACD', which has length 3.

Practice Question 2

What is time complexity of LCS of two strings of size M and N using DP?

A) O(M * N)

B) O(M + N)

C) O(2^(M+N))

D) O(log(M*N))

Correct Answer: A) O(M * N)

Step-by-step Solution: The DP table size is M x N. Filling each cell takes O(1) time. Total time complexity = O(M * N).

Draw the DP table and trace the character matching arrows to understand the backtracking recovery path.