Longest Common Subsequence

The problem

Given two strings text1 and text2, return the length of their longest common subsequence: the longest string you can get from both by deleting some letters, without changing the order of the rest. If they share no letters, return 0.

Example 1

Input: text1 = "ocean", text2 = "clean"

Output: 4

Drop the “o” from “ocean” and the “l” from “clean”, and both become “cean”.

text1

ocean

text2

clean

Example 2

Input: text1 = "abc", text2 = "xyz"

Output: 0

No letter appears in both.

Example 3

Input: text1 = "stone", text2 = "notes"

Output: 2

For example “oe” or “te”. The words share all five letters, but in different orders.

Constraints

• 1 ≤ text1.length, text2.length ≤ 1000 (call them m and n)
• Only lowercase English letters.

Clarifying questions

Must the common letters be next to each other?

No. A subsequence may skip letters, as long as the order is kept.

Do we return the subsequence or its length?

Only the length.

Can a letter be matched twice?

No. Each letter of each string is used at most once.

Spot the pattern

Compare the last letters of the two strings. If they are equal, they can be matched with each other, and the rest is the same question on both strings minus one letter. If not, at least one of them is unused, so drop it and ask again. Answers for pairs of prefixes, built from smaller pairs that repeat, are dynamic programming on a two-dimensional table.

Solutions

Full tableO(m × n)Two rowsO(m × n)

Show all

There is no brute force tab. Trying every subsequence of one string against the other takes 2ᵐ tries, and the plain recursion on prefixes is also exponential. The table is the standard first answer.

Full table O(m × n)

The idea

Let common_length[i][j] be the answer for the first i letters of text1 and the first j letters of text2. Row 0 and column 0 stand for an empty prefix, so they are 0. For every other cell, look at the last letters of the two prefixes, text1[i - 1] and text2[j - 1]:

• Equal: match them. common_length[i][j] = common_length[i - 1][j - 1] + 1, the diagonal cell plus one.
• Different: one of them is not used. common_length[i][j] is the larger of the cell above (drop the letter from text1) and the cell to the left (drop it from text2).

Fill the table row by row. The answer is common_length[m][n].

Why it is correct: if the last letters are equal, some best answer uses them as its last match. If they differ, a common subsequence cannot end with both, so dropping one of them loses nothing, and the max tries both.

Walkthrough

	""	c	l	e	a	n
""	0	0	0	0	0	0
o	0
c	0
e	0
a	0
n	0

1. common_length = (len(text1) + 1) × (len(text2) + 1) table of zeros
2. for i in 1 .. len(text1): for j in 1 .. len(text2):
3. if text1[i - 1] == text2[j - 1]:
4. common_length[i][j] = common_length[i - 1][j - 1] + 1
5. else:
6. common_length[i][j] = max(common_length[i - 1][j], common_length[i][j - 1])
7. return common_length[len(text1)][len(text2)]

Row i stands for the first i letters of "ocean", column j for the first j letters of "clean". Row 0 and column 0 are empty prefixes, which share nothing, so they are all 0.

← BackStep →Play1 / 9

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Table: commonLength[i][j] is the answer for the first i letters of text1 and the first
    // j letters of text2. Each cell looks at three neighbors: O(m × n) time and space.
    public int longestCommonSubsequence(String text1, String text2) {
        int text1Length = text1.length(), text2Length = text2.length();
        // Row 0 and column 0 stand for an empty prefix, which shares nothing.
        int[][] commonLength = new int[text1Length + 1][text2Length + 1];
        for (int i = 1; i <= text1Length; i++) {
            for (int j = 1; j <= text2Length; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    // Equal last letters: use them, plus the best for both prefixes without them.
                    commonLength[i][j] = commonLength[i - 1][j - 1] + 1;
                } else {
                    // Different: one of the two last letters is not used.
                    commonLength[i][j] = Math.max(commonLength[i - 1][j], commonLength[i][j - 1]);
                }
            }
        }
        return commonLength[text1Length][text2Length];
    }
}

Big O

Time O(m × n)Space O(m × n)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The inner loop fills one cell with one comparison and an addition or a max. That is a fixed job, so each cell filled counts as 1 step.

   1. common_length = (len(text1) + 1) × (len(text2) + 1) table of zeros
   2. for i in 1 .. len(text1): for j in 1 .. len(text2):
   3. if text1[i - 1] == text2[j - 1]:
   4. common_length[i][j] = common_length[i - 1][j - 1] + 1
   5. else:
   6. common_length[i][j] = max(common_length[i - 1][j], common_length[i][j - 1])
   7. return common_length[len(text1)][len(text2)]

2. 2 Count the runs on Example 1

   The table has one column per letter of “ocean”. Each row fills one cell per letter of “clean”.

   5 + 5 + 5 + 5 + 5 = 25 cells.

   row	1 "o"	2 "c"	3 "e"	4 "a"	5 "n"
   cells filled	5	5	5	5	5

   total

   5 × 5 = 25 cells

3. 3 Write the count for any n

   m × n cells

   Check it with Example 1: 5 × 5 = 25. That matches the count.

4. 4 Keep only the part that grows fastest

   Nothing to drop. It is O(m × n): at most a million steps for two strings of 1000 letters.

   So the time is O(m × n).

5. S Space: count the extra memory the same way

   The table holds (m + 1) × (n + 1) numbers. So the space is O(m × n).

   common_length table ((m + 1) × (n + 1))

Two rows O(m × n)

The idea

A cell reads only three others: the one above, the one on the diagonal above-left, and the one to its left. The first two are in the previous row, and the last is in the current row. So keep just two rows: previous_row and current_row.

Fill current_row left to right with the same rule, reading previous_row[j - 1], previous_row[j] and current_row[j - 1]. When the row is done, current_row becomes previous_row and a fresh current_row starts.

Why it is correct: it computes the same numbers as the full table, in the same order, and only drops rows that are never read again.

Walkthrough

text2

""clean

previous_row

000000

1. previous_row = [0] * (len(text2) + 1)
2. for i in 1 .. len(text1):
3. current_row = [0] * (len(text2) + 1)
4. for j in 1 .. len(text2):
5. if letters match: current_row[j] = previous_row[j - 1] + 1
6. else: current_row[j] = max(previous_row[j], current_row[j - 1])
7. previous_row = current_row
8. return previous_row[len(text2)]

A table cell only reads the row above it (above and diagonal) and the cell to its left. So keep two rows: previous_row, the row above, and current_row, the row being filled.

← BackStep →Play1 / 11

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Two rows: each row of the table only reads the row above it, so keep the
    // previous row and the current one. O(m × n) time, O(n) space.
    public int longestCommonSubsequence(String text1, String text2) {
        int text2Length = text2.length();
        int[] previousRow = new int[text2Length + 1];
        for (int i = 1; i <= text1.length(); i++) {
            // cur[0] stays 0: an empty prefix of text2 shares nothing.
            int[] currentRow = new int[text2Length + 1];
            for (int j = 1; j <= text2Length; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    // Equal last letters: use them, plus the best for both prefixes without them.
                    currentRow[j] = previousRow[j - 1] + 1;
                } else {
                    // Different: one of the two last letters is not used.
                    currentRow[j] = Math.max(previousRow[j], currentRow[j - 1]);
                }
            }
            previousRow = currentRow;
        }
        return previousRow[text2Length];
    }
}

Big O

Time O(m × n)Space O(n)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   Same as the full table: each cell filled is 1 step.

   1. previous_row = [0] * (len(text2) + 1)
   2. for i in 1 .. len(text1):
   3. current_row = [0] * (len(text2) + 1)
   4. for j in 1 .. len(text2):
   5. if letters match: current_row[j] = previous_row[j - 1] + 1
   6. else: current_row[j] = max(previous_row[j], current_row[j - 1])
   7. previous_row = current_row
   8. return previous_row[len(text2)]

2. 2 Count the runs on Example 1

   The same 5 rows of 5 cells.

   25 cells.

   row	1 "o"	2 "c"	3 "e"	4 "a"	5 "n"
   cells filled	5	5	5	5	5

   total

   5 × 5 = 25 cells

3. 3 Write the count for any n

   m × n cells

   Check it with Example 1: 5 × 5 = 25. That matches the count.

4. 4 Keep only the part that grows fastest

   Nothing to drop. The time is still O(m × n). Only the memory improves.

   So the time is O(m × n).

5. S Space: count the extra memory the same way

   Two rows of n + 1 numbers. So the space is O(n). Passing the shorter string as text2 makes it O(min(m, n)).

   previous_row (n + 1)current_row (n + 1)

Common mistake

Using the cell to the left when the letters match

On a match, the answer is the diagonal plus one, not the left or upper cell plus one. Using a neighbor that already counts one of the two letters would match a letter twice. With “a” against “aa”, it would give 2 instead of 1.

Tested at the limits

2,000 random pairs of texts of 1 to 8 letters, using only a and b, or a, b and c, so letters repeat often. The full table and the two rows gave the same answer every time, and matched a check that tries every subsequence.

Largest inputs	Result
Two texts of 1,000 letters (the most allowed), random letters a to d. Two rows.	0.09 s, and about 0.04 MB of extra memory: two rows of 1,001 counts.
The same two texts. Full table.	0.1 s, and about 11 MB of extra memory: a table of 1,001 x 1,001 counts. The two rows give the same answer with far less memory.