LCS definition
- Algorithms course
- Advanced
- Lesson 9/56
- 4 min
The longest common subsequence of two sequences.
LCS definition
The longest common subsequence (LCS) is the longest subsequence common to two sequences. Order is preserved, contiguity is not required.
Example: for "ABCBDAB" and "BDCAB" the LCS is "BCAB" of length 4.
LCS is used in DNA alignment, diff tools and spell checking; it is an important DP problem.
Subsequence vs substring
A subsequence preserves order but need not be contiguous. A substring must be contiguous.
LCS uses the subsequence definition; this is why it is more flexible.
This distinction is the key difference between LCS and longest common substring.
Practice LCS length trial
Write lcs_brute(s1, s2). Find the LCS length of two sequences by brute force. Print 2 with print(lcs_brute("ABC", "AC")).
Starter code
def lcs_brute(s1, s2):
# LCS brute-forceSample solution
def lcs_brute(s1, s2):
# LCS brute-force
if not s1 or not s2:
return 0
if s1[0] == s2[0]:
return 1 + lcs_brute(s1[1:], s2[1:])
return max(lcs_brute(s1[1:], s2), lcs_brute(s1, s2[1:]))
print(lcs_brute("ABC", "AC"))Expected output
2
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Which definition does LCS use?
- Prefix
- Substring
- Subsequence Correct answer
- Suffix
Explanation: Subsequence.
2 LCS abbreviation
LCS: Longest Common ____LCS: Longest Common SubsequenceExplanation: Subsequence is right.
3 LCS definition: match the terms
| Term | Meaning |
|---|---|
LCS |
Common subseq |
subsequence |
Ordered |
substring |
Contiguous |
DP |
Dynamic |