DSA

LCS and edit distance: longest common subsequence and string edits

Use a pair of prefixes as the state for LCS, edit distance and counting subsequences, and a range of one string as the state for palindromes.

5,844 words · 26 min read

Part 1 of 10 Longest common subsequence

The longest common subsequence

A DP state can be a position in a list, a cell of a grid, or a number of items together with a capacity. Most problems in this lesson compare two strings: they ask how much the strings have in common, or how many changes turn one into the other. The best-known of them asks for the longest common subsequence, or LCS for short.

A subsequence of a string is what remains after deleting some of its characters, possibly none, and keeping the rest in order. ple is a subsequence of plate: delete the a and the t. pea is not, because in plate the a comes before the e. A common subsequence of two strings is a subsequence of both. ple is also a subsequence of apple, so it is a common subsequence of plate and apple.

You get two strings, text1 and text2. Return the length of their longest common subsequence: the longest string that is a subsequence of both. If they have none, return 0.

A subsequence of a string keeps some of its characters, possibly none or all, in their original order and deletes the rest.

Constraints

  • Each string has 1 to 1,000 characters
  • Only lowercase English letters

Sample 1 · Input

text1 = "abcde", text2 = "ace"

Output

3

Sample 2 · Input

text1 = "abc", text2 = "abc"

Output

3

Sample 3 · Input

text1 = "abc", text2 = "def"

Output

0

In the first sample ace is a subsequence of abcde, so the whole second string is a common subsequence, of length 3. In the third sample the strings share no letter, and their only common subsequence is the empty one.

Our example for this problem is plate and apple. Their common subsequence ple has length 3, and none is longer. The only other letter the two words share is a. In plate the a comes after the p and the l, and in apple it comes before them, so a common subsequence that uses the a can use neither of those letters. It is then a or ae, two characters at most.

A program could list every subsequence of the first string and check each one against the second. Every character is either kept or deleted, so a string of nn characters has 2n2^n ways to choose a subsequence: 32 for plate, 1,048,576 for a string of 20 characters, and a number with 302 digits for a string of 1,000 characters, the longest this problem allows.