Longest Common Subsequence

Problem statement

Given two strings, return the length of their longest common subsequence. A subsequence keeps order but need not be contiguous. If they share nothing, return 0.

Example:

Input:

text1 = "abcde", text2 = "ace"

Expected output:

3

Why: "ace" is in both. "aec" is not — e cannot come before c in text1.

"abc" and "def" share nothing, so 0.

Practice on LeetCode: Longest Common Subsequence

What we are pairing

This is not Longest Palindromic Substring. A substring is a contiguous slice. A subsequence may drop characters. "ace" is a subsequence of "abcde". It is not a substring.

Stand at (i, j) — the remaining suffixes text1[i:] and text2[j:].

If the two letters match, you take that letter and move both indices. If they do not, you drop a letter from one string or the other, and keep the longer option:

long(i, j) = 1 + long(i+1, j+1)                    if text1[i] == text2[j]
long(i, j) = max(long(i+1, j), long(i, j+1))       otherwise
long(past either end) = 0

On "abcde" / "ace" the first letters match (a), so the answer is 1 + long("bcde", "ce"). Later c matches c, then e matches e. Three takes.

When the letters miss, both skips are live. long("bcde", "ce") compares dropping b against dropping c. Dropping b is the one that still lets c meet c.

Why not list every subsequence

text1 has 2^n subsequences. Checking each as a subsequence of text2 will not run.

The state is only the pair (i, j). That is n · m cells. The same pair is asked from many miss-branches — long(3, 1) shows up after different skip sequences. Remember each pair.

Bottom-up fills the same recurrence from the ends of both strings back to (0, 0). One rolling row is enough if you want O(min(n, m)) extra space.

Golang Solution

dp[i][j] is the LCS length of the two suffixes. Uncomputed cells are -1 (0 is a real answer). The helper writes the cell, then returns it. The top-left cell is the answer.

Time: O(n · m) — each pair is solved once
Space: O(n · m) — table, plus O(n + m) recursion depth

func longestCommonSubsequence(text1 string, text2 string) int {
    dp := make([][]int, len(text1))
    for j := 0; j < len(text1); j++ {
        dp[j] = make([]int, len(text2))
        for i := 0; i < len(text2); i++ {
            dp[j][i] = -1
        }
    }
    dp[0][0] = long(text1, text2, dp, 0, 0)
    return dp[0][0]
}

func long(text1 string, text2 string, dp [][]int, i, j int) int {

    if i >= len(text1) || j >= len(text2) {
        return 0
    }

    if dp[i][j] > -1 {
        return dp[i][j]
    }

    if text1[i] == text2[j] {
        dp[i][j] = 1 + long(text1, text2, dp, i+1, j+1)
    } else {
        dp[i][j] = max(long(text1, text2, dp, i+1, j), long(text1, text2, dp, i, j+1))
    }

    return dp[i][j]
}

n and m are at least 1, so dp[0][0] exists. Two identical strings return the shared length. Two strings with no shared letter fill the table with zeros.