Longest Common Subsequence in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the Longest Common Subsequence (LCS)?

LCS is the longest sequence that appears in the same relative order in two sequences but not necessarily contiguously.

beginner

What is the main difference between Longest Common Subsequence and Longest Common Substring?

LCS allows characters to be non-contiguous but in order, while Longest Common Substring requires characters to be contiguous.

intermediate

In LCS dynamic programming, what does the table cell dp[i][j] represent?

dp[i][j] stores the length of the LCS of the first i characters of string1 and first j characters of string2.

intermediate

What is the time complexity of the classic dynamic programming solution for LCS?

The time complexity is O(m*n), where m and n are the lengths of the two input strings.

advanced

How do you reconstruct the LCS string from the dp table after computing lengths?

Start from dp[m][n], move backwards: if characters match, add to LCS and move diagonally; else move in direction of larger dp value.

What does the Longest Common Subsequence represent?

A Longest sequence appearing in order in both strings, not necessarily contiguous

B Longest sequence appearing contiguously in both strings

C Shortest sequence common to both strings

D Longest sequence appearing in reverse order in both strings

LCS is the longest sequence that appears in the same order in both strings but characters do not have to be next to each other.

In LCS dynamic programming, if characters at positions i and j match, what is dp[i][j]?

A max(dp[i-1][j], dp[i][j-1])

B dp[i-1][j-1] + 1

C dp[i-1][j-1]

D 0

When characters match, we add 1 to the LCS length found by excluding these characters (dp[i-1][j-1] + 1).

What is the base case for the dp table in LCS?

A dp[0][j] = 0 and dp[i][0] = 0 for all i, j

B dp[0][j] = j and dp[i][0] = i

C dp[0][j] = 1 and dp[i][0] = 1

D dp[0][j] = -1 and dp[i][0] = -1

If one string is empty, LCS length is zero, so dp[0][j] and dp[i][0] are zero.

What is the time complexity of the classic LCS dynamic programming solution?

A O(m+n)

B O(m^2)

C O(m*n)

D O(n^2)

The solution fills an m by n table, so time complexity is O(m*n).

Which of these is NOT true about LCS?

A LCS can be used to find similarity between strings

B LCS characters must appear in order in both strings

C LCS length can be zero if no common characters

D LCS characters must be contiguous in both strings

LCS characters do not need to be contiguous, only in order.

Explain how to use dynamic programming to find the Longest Common Subsequence between two strings.

Think about how to build solutions for smaller prefixes of the strings.

Describe the process to reconstruct the actual LCS string after computing the dp table.

Trace back from the bottom-right corner of the dp table.