Longest Common Subsequence

Medium

The problem

A subsequence keeps some of the characters of a string in their original order, possibly skipping some. Return the length of the longest subsequence that text1 and text2 have in common, or 0 if they share none.

Example 1
Input: text1 = "abcde", text2 = "ace"
Output: 3
"ace" appears in both.
Example 2
Input: text1 = "abc", text2 = "abc"
Output: 3
Example 3
Input: text1 = "abc", text2 = "def"
Output: 0
They share no letters.

Limits

1 ≤ len(text1), len(text2) ≤ 1,000
Both strings have only lowercase English letters

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

Compare the last characters of the two prefixes. If equal, they extend the answer; if not, one of them is dropped.

The idea

dp[i][j] = dp[i−1][j−1] + 1 if a[i−1]==b[j−1], else max(dp[i−1][j], dp[i][j−1]).

Target: O(m·n) time

Go function shape

func longestCommonSubsequence(text1 string, text2 string) int

Reference solution

Tested with go test. Try it yourself first, then compare.

// LongestCommonSubsequence.
// State: dp[i][j] = LCS length of a[:i] and b[:j]. Row 0 and column 0 are the empty-prefix base cases.
func LongestCommonSubsequence(a, b string) int {
	dp := make([][]int, len(a)+1)
	for i := range dp {
		dp[i] = make([]int, len(b)+1)
	}
	for i := 1; i <= len(a); i++ {
		for j := 1; j <= len(b); j++ {
			if a[i-1] == b[j-1] {
				dp[i][j] = dp[i-1][j-1] + 1 // match: extend the diagonal
			} else {
				dp[i][j] = max(dp[i-1][j], dp[i][j-1]) // drop one character
			}
		}
	}
	return dp[len(a)][len(b)]
}

Read the lesson: 2-D Dynamic Programming