Problem 31.3 · DP on Strings and SequencesMedium

Longest Common Subsequence

What it teaches: The two-sequence table: diagonal on a match, best neighbour otherwise.

Practise it on judges as “Longest Common Subsequence”.

The problem

Return the length of the longest subsequence common to both strings.

Example 1

Input: text1 = "abcde", text2 = "ace"
Output: 3

Constraints

1 ≤ lengths ≤ 1000

Pattern clues in the wording

→ Two strings, common subsequence

These clues point to DP on Two Strings: dp[i][j] answers the question for the first i characters of one string and the first j of the other.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	text1 = "abcde" text2 = "ace"	3
2	text1 = "abc" text2 = "abc"	3
3	text1 = "abc" text2 = "def"	0

From slow to fast

Approaches

1. 2D table · O(m × n)2. One row · O(m × n)

2D table

Time O(m × n) Space O(m × n)

(m + 1) × (n + 1) table filled row by row.

Approach 1

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                dp[i][j] = text1.charAt(i - 1) == text2.charAt(j - 1)
                        ? dp[i - 1][j - 1] + 1
                        : Math.max(dp[i - 1][j], dp[i][j - 1]);
        return dp[m][n];
    }
}

Verdict: Clear; easy to reconstruct the subsequence.

One row

Time O(m × n) Space O(n)

Keep a single row plus the saved diagonal value.

Approach 2

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int n = text2.length();
        int[] dp = new int[n + 1];
        for (int i = 1; i <= text1.length(); i++) {
            int diag = 0;                       // dp[i-1][j-1]
            for (int j = 1; j <= n; j++) {
                int up = dp[j];
                dp[j] = text1.charAt(i - 1) == text2.charAt(j - 1) ? diag + 1 : Math.max(up, dp[j - 1]);
                diag = up;
            }
        }
        return dp[n];
    }
}

Verdict: Memory-light.

Before you submit

Edge cases and common mistakes

Test these inputs

No common characters (0)
Identical strings

Mistakes people make

Losing the diagonal value when rolling rows.

Interview

Follow-up questions

How do you print the LCS itself?

Command Palette