Algorithms and Data Structures · Middle · Question 45 of 75

What is the longest common subsequence (LCS) of two strings?

✓Correct answer: The longest common sequence in order, gaps allowed
2The longest substring that both strings share contiguously
3The longest prefix that both strings start with

Explanation

For "ABCBDAB" and "BDCABA" one LCS is "BCBA". The standard DP table is O(n × m). LCS is the idea behind diff tools.

Further reading

Test yourself

Take the Algorithms and Data Structures · Middle quiz: questions and options are shuffled, and you get a review of your mistakes at the end.