Longest Common Subsequence

Free with account Updated Nov 19, 2026 · 6 min read
On this page

    Problem statement

    Given two strings text1 and text2, return the length of their longest common subsequence, or 0 if they share no characters. A subsequence keeps the original order of characters but may skip any of them: "one" is a subsequence of "stone", while "eno" is not.

    The classic two-string DP. It is the backbone of diff, version-control merges and DNA alignment, and the same table shape solves Edit Distance and many string questions after it. Original problem: LeetCode 1143.

    Example

    o, n and e appear in both words in the same order, so the longest common subsequence has length 3.
    o, n and e appear in both words in the same order, so the longest common subsequence has length 3.
    Input:  text1 = "stone", text2 = "longest"
    Output: 3          # "one"
    Input:  text1 = "abcd", text2 = "bcda"
    Output: 3          # "bcd"
    Input:  text1 = "abc", text2 = "def"
    Output: 0

    Constraints (assumed)

    • 1 ≤ length of each string ≤ 1,000.
    • Lowercase English letters.

    What this question tests

    • Defining a 2D state over prefixes and the two-case recurrence (letters equal / not equal).
    • Seeing why a greedy match fails, which is the reason DP is needed.
    • Optimising memory to two rows and reconstructing the subsequence itself.

    Questions to ask first

    1. Subsequence or substring? A substring must be contiguous and uses a different recurrence. (Here: subsequence.)
    2. Do you want the length or the subsequence itself? (Here: length; the string is a follow-up.)
    3. How long can the strings be? O(n · m) time is fine up to a few thousand each.
    4. Is the comparison case-sensitive? (Here: lowercase only.)