LCS definition

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.

Exercise 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")).

Show example 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"))

Test yourself

Which definition does LCS use?
- Prefix
- Substring
- Subsequence
- Suffix
Show answer

Subsequence — Subsequence.

LCS abbreviation

LCS: Longest Common ____

Show answer

LCS: Longest Common Subsequence

LCS definition: match the terms

LCS

Common subseq
subsequence

Ordered
substring

Contiguous
DP

Dynamic

Next lesson: DP table

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies