Longest Common Subsequence in DSA Typescript - 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.

intermediate

How does dynamic programming help in finding LCS?

It breaks the problem into smaller overlapping subproblems and stores their results to avoid repeated work, building up the solution efficiently.

intermediate

What does the DP table represent in LCS algorithm?

Each cell dp[i][j] stores the length of LCS of the first i characters of string A and first j characters of string B.

beginner

In LCS, what happens when characters at current indices match?

We add 1 to the LCS length found by excluding these characters, i.e., dp[i][j] = 1 + dp[i-1][j-1].

intermediate

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

It is O(m * n), where m and n are the lengths of the two input sequences.

What does LCS stand for?

A Least Common Substring

B Largest Common Substring

C Longest Continuous Sequence

D Longest Common Subsequence

LCS stands for Longest Common Subsequence, which is a sequence appearing in the same order in both strings.

If characters at current indices of both strings match, what is the LCS relation?

A dp[i][j] = 1 + dp[i-1][j-1]

B dp[i][j] = max(dp[i-1][j], dp[i][j-1])

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

D dp[i][j] = 0

When characters match, we add 1 to the LCS length found by excluding these characters.

What is stored in dp[i][j] in the LCS DP table?

A Length of LCS of first i characters of string A and first j characters of string B

B Length of longest substring ending at i and j

C Number of matching characters at i and j

D Sum of ASCII values of matched characters

dp[i][j] stores the length of the longest common subsequence of the first i characters of string A and first j characters of string B.

What is the time complexity of the classic LCS algorithm using DP?

A O(m + n)

B O(m * n)

C O(m^2 + n^2)

D O(2^(m+n))

The classic DP solution for LCS runs in O(m * n) time, where m and n are the lengths of the two strings.

If characters at current indices do not match, how is dp[i][j] computed?

A dp[i][j] = dp[i-1][j-1]

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

C dp[i][j] = max(dp[i-1][j], dp[i][j-1])

D dp[i][j] = 0

If characters don't match, dp[i][j] is the maximum LCS length by excluding one character from either string.

Explain how the dynamic programming table is built for the Longest Common Subsequence problem.

Think about how smaller problems help solve bigger ones step by step.

Describe the difference between Longest Common Subsequence and Longest Common Substring.

One cares about order, the other about continuous matching.