Longest Common Subsequence

The problem

A subsequence of a string is what remains after you delete some of its letters, or none, without changing the order of the rest. Given two strings a and b, return the length of the longest string that is a subsequence of both. If they have no letter in common, or if either string is empty, return 0.

What to write

function solve(a: string, b: string): number

Input
a = "abcde"
b = "ace"

Output
3

Input
a = "abc"
b = "def"

Output
0

Constraints

0–200 lowercase characters per string.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   Each string has at most 200 letters, so there are at most 200 × 200 = 40000 pairs of positions, one from each string. Doing a little work per pair is fast. Trying every subsequence is not: each letter of a 200-letter string can be kept or dropped, which gives 2 to the power 200 choices.

2. Hint 2: Ask a smaller question

   Take "abcde" and "ace". Both end in e. Is there any reason not to pair those two e's in a longest common subsequence? Now take "abcd" and "ace", which end in different letters. Can d and e both be the last letter of the same common subsequence?

3. Hint 3: Name the pattern

   Look at the two last letters. If they are equal, pair them and solve the rest. If not, at least one of them is unused: try dropping each and keep the better result. Each smaller problem is a pair of prefixes, the first few letters of each string. A table over two prefix lengths is two-dimensional dynamic programming. Read the lesson on two-dimensional dynamic programming.

4. Hint 4: State the invariant

   The cell in row i and column j holds the length of the longest common subsequence of the first i letters of a and the first j letters of b. Row 0 and column 0 stand for an empty prefix and hold 0. Every other cell needs only the cells above, left and up-left of it.

5. Hint 5: Sketch the pseudocode

   Table of zeros: one more row than a has letters, one more column than b has. For each row i and column j, both from 1: if the i-th letter of a equals the j-th letter of b, cell = 1 + the up-left cell; otherwise cell = the larger of the cells above and left. Return the bottom-right cell.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Use a grid over prefix lengths. Matching last characters extend the diagonal result; otherwise take the better result from skipping a character in either string.

The slow way

A subsequence is what remains of a string after deleting some letters without reordering the rest. The slow way lists every subsequence of a, checks each against b and keeps the longest that fits. Each letter is kept or dropped, so "abcde" has 32 choices and a string of 200 letters has 2 to the power 200.

The insight

Compare only the last letters of the two strings. If they are equal, some longest common subsequence ends with that pair, so the answer is 1 plus the answer without those two letters. If they differ, at least one of them is unused, so the answer is the better of dropping one or the other. Every smaller question is about two prefixes: the first few letters of each string.

Step by step

1. Make a table of zeros with one cell for every pair of prefix lengths. Row i stands for the first i letters of a, column j for the first j letters of b. Row 0 and column 0 stand for an empty prefix, which shares nothing with any string, so their zeros are final.
2. Go through the cells row by row, skipping row 0 and column 0. A cell reads the cells above it, on its left, and up and to its left. Going row by row and left to right fills all three before the cell that needs them.
3. Compare the last letters of the two prefixes. The cell is about the first i letters of a and the first j letters of b. Their last letters decide which rule applies. Counting from 0, they sit at positions i - 1 and j - 1.
4. Same letter: one more than the cell up and to the left. Pair the two equal letters. What is left is both prefixes without their last letter, and the cell up and to the left already holds the best length for those. The pair adds 1 to that length.
5. Different: the larger of the cell above and the cell on the left. Two different last letters cannot both end the same common subsequence, so at least one is unused. The cell above drops the last letter of a; the cell on the left drops the last letter of b. Take the better.
6. Return the bottom-right cell: the answer for the two whole strings. The last row stands for all of a and the last column for all of b. If either string is empty, no cell is filled and that cell is one of the starting zeros.

The same numbered steps are the comments in each solution.

function solve(a, b) {
  // 1. Make a table of zeros with one cell for every pair of prefix lengths
  const dp = Array.from({ length: a.length + 1 }, () =>
    Array(b.length + 1).fill(0),
  );
  // 2. Go through the cells row by row, skipping row 0 and column 0
  for (let i = 1; i <= a.length; i++)
    for (let j = 1; j <= b.length; j++) {
      // 3. Compare the last letters of the two prefixes
      if (a[i - 1] === b[j - 1]) {
        // 4. Same letter: one more than the cell up and to the left
        dp[i][j] = 1 + dp[i - 1][j - 1];
      } else {
        // 5. Different: the larger of the cell above and the cell on the left
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  // 6. Return the bottom-right cell: the answer for the two whole strings
  return dp[a.length][b.length];
}

function solve(a: string, b: string): number {
  // 1. Make a table of zeros with one cell for every pair of prefix lengths
  const dp = Array.from({ length: a.length + 1 }, () =>
    Array(b.length + 1).fill(0),
  );
  // 2. Go through the cells row by row, skipping row 0 and column 0
  for (let i = 1; i <= a.length; i++)
    for (let j = 1; j <= b.length; j++) {
      // 3. Compare the last letters of the two prefixes
      if (a[i - 1] === b[j - 1]) {
        // 4. Same letter: one more than the cell up and to the left
        dp[i][j] = 1 + dp[i - 1][j - 1];
      } else {
        // 5. Different: the larger of the cell above and the cell on the left
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  // 6. Return the bottom-right cell: the answer for the two whole strings
  return dp[a.length][b.length];
}

def solve(a, b):
    # 1. Make a table of zeros with one cell for every pair of prefix lengths
    dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    # 2. Go through the cells row by row, skipping row 0 and column 0
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            # 3. Compare the last letters of the two prefixes
            if a[i - 1] == b[j - 1]:
                # 4. Same letter: one more than the cell up and to the left
                dp[i][j] = 1 + dp[i - 1][j - 1]
            else:
                # 5. Different: the larger of the cell above and the cell on the left
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    # 6. Return the bottom-right cell: the answer for the two whole strings
    return dp[len(a)][len(b)]

Example 1, traced

Input
a = "abcde"
b = "ace"

Output
3

Why it works

Every cell holds one answer: the length of the longest common subsequence of a prefix of a and a prefix of b. The zeros for an empty prefix are correct. Each rule gives a correct cell whenever the cells it reads are correct, and those are filled earlier. So every cell is correct, including the last. Building answers from smaller ones this way is dynamic programming.

Time and space

Time O(n × m), extra space O(n × m). With n and m the lengths of the two strings, the table has (n + 1) × (m + 1) cells, and a cell costs at most one comparison and one maximum. So the time and the space are both O(n × m).

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Row i stands for the first i letters, so its last letter is at position i - 1. Comparing positions i and j reads past the end: Python stops with an error, and JavaScript returns 1 for "abc" and "def".
• On equal letters, add 1 to the cell up and to the left. The cells above and on the left may already use one of the two letters, pairing it twice: with the left one, "a" and "aa" give 2.
• On different letters, carry the better neighbor forward. Writing 0 there throws away everything found so far: "abcde" with "ace" would give 1, because only the final pair of e's is counted.

Pattern

Two-dimensional dynamic programming. Builds on Unique Paths.

Keep going