☕ DSA Java Articles

Topics › Dynamic Programming › DP on Strings

Longest common subsequence

Hard TUF ID 308 A2ZSDEBlind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Given two strings s1 and s2, return the length of their longest common subsequence (LCS). A subsequence is what remains after deleting zero or more characters without changing the order of the rest: "ace" is a subsequence of "abcde", but "aec" is not. A common subsequence appears as a subsequence in both strings. If there is none, the answer is 0.

Constraints (LeetCode 1143): 1 ≤ n, m ≤ 1000, lowercase English letters. The Java methods also accept empty strings.

Example 1

s1 = "abcde", s2 = "ace"
answer = 3          // "ace" is a subsequence of both

Example 2

s1 = "abc", s2 = "def"
answer = 0          // no character is shared

Why this is a DP problem

Listing every subsequence of s1 (there are 2^n) and testing each against s2 is hopeless for n = 1000. Instead, compare the strings from the back. Write f(i, j) for the LCS length of the prefixes s1[0..i) and s2[0..j). Using prefix lengths rather than last indices means the base case is simply “one prefix is empty”, there are no -1 indices, and the tabulation can use row 0 and column 0 as that base case.

Look at the last characters s1[i - 1] and s2[j - 1]:

This “match the ends or drop one end” reasoning is the template for most of the DP on Strings section.

Approach 1: Recursion

Intuition. Implement the recurrence directly. When characters differ we try both ways of dropping one character and keep the better.

Algorithm.

  1. If i == 0 or j == 0, return 0.
  2. If s1[i - 1] == s2[j - 1], return 1 + f(i - 1, j - 1).
  3. Otherwise return max(f(i - 1, j), f(i, j - 1)).
static int recursive(String s1, String s2) {
    return solve(s1.length(), s2.length(), s1, s2);
}

/** LCS length of the prefixes s1[0..i) and s2[0..j). */
static int solve(int i, int j, String s1, String s2) {
    if (i == 0 || j == 0) return 0;                          // an empty prefix shares nothing
    if (s1.charAt(i - 1) == s2.charAt(j - 1)) return 1 + solve(i - 1, j - 1, s1, s2);
    return Math.max(solve(i - 1, j, s1, s2), solve(i, j - 1, s1, s2));
}

Complexity. Time O(2^(n + m)) in the worst case: when nothing matches, every call branches twice and the depth is up to n + m. Space O(n + m) for the recursion stack.

Approach 2: Memoization

Intuition. There are only (n + 1)(m + 1) distinct pairs (i, j), yet the recursion reaches the same pair along many paths (drop from s1 then s2, or the other way round). Cache each answer in dp[i][j], using -1 for “not computed” because real lengths are never negative.

Algorithm.

  1. Create dp[n + 1][m + 1] filled with -1.
  2. Run the recursion, returning dp[i][j] when it is already known and storing every result before returning it.
static int memoization(String s1, String s2) {
    int n = s1.length(), m = s2.length();
    int[][] dp = new int[n + 1][m + 1];
    for (int[] row : dp) Arrays.fill(row, -1);
    return memo(n, m, s1, s2, dp);
}

static int memo(int i, int j, String s1, String s2, int[][] dp) {
    if (i == 0 || j == 0) return 0;
    if (dp[i][j] != -1) return dp[i][j];
    if (s1.charAt(i - 1) == s2.charAt(j - 1)) return dp[i][j] = 1 + memo(i - 1, j - 1, s1, s2, dp);
    return dp[i][j] = Math.max(memo(i - 1, j, s1, s2, dp), memo(i, j - 1, s1, s2, dp));
}

Complexity. Time O(n · m): each state is computed once in constant time. Space O(n · m) for the table plus O(n + m) stack. The stack depth is at most about 2000 frames, which the default JVM stack handles.

Approach 3: Tabulation

Intuition. Every state reads only states with a smaller i, a smaller j, or both. Filling the table row by row, left to right, guarantees those are ready. Row 0 and column 0 are the empty-prefix base case and are already 0 in a new Java array.

Algorithm.

  1. Create dp[n + 1][m + 1] (all zeros).
  2. For i = 1 .. n, j = 1 .. m: apply the recurrence.
  3. Return dp[n][m].
static int tabulation(String s1, String s2) {
    int n = s1.length(), m = s2.length();
    int[][] dp = new int[n + 1][m + 1];                      // dp[0][*] = dp[*][0] = 0 by default
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) dp[i][j] = 1 + dp[i - 1][j - 1];
            else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[n][m];
}

Dry run on Example 1 (s1 down the side, s2 across the top):

  ”” a c e
”” 0 0 0 0
a 0 1 1 1
b 0 1 1 1
c 0 1 2 2
d 0 1 2 2
e 0 1 2 3

The bold cells are the matches a, c, e, each one more than its upper-left neighbour. Every other cell copies the larger of the cell above and the cell to the left. The answer is dp[5][3] = 3.

Complexity. Time O(n · m), space O(n · m).

Approach 4: Space optimized

Intuition. Row i reads only row i - 1 (above and upper-left) and row i itself (left). Keep two arrays, prev for row i - 1 and cur for row i, and swap them after each row. cur[0] is never written, so it stays 0, which is the correct base case for every row.

Algorithm.

  1. prev and cur of length m + 1, all zeros.
  2. For each i, fill cur[1..m] from prev and cur, then swap the two arrays.
  3. After the last swap, prev holds row n; return prev[m].
static int spaceOptimized(String s1, String s2) {
    int n = s1.length(), m = s2.length();
    int[] prev = new int[m + 1], cur = new int[m + 1];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) cur[j] = 1 + prev[j - 1];
            else cur[j] = Math.max(prev[j], cur[j - 1]);
        }
        int[] tmp = prev; prev = cur; cur = tmp;             // the row just built becomes "previous"
    }
    return prev[m];
}

Complexity. Time O(n · m), space O(m). Passing the shorter string as s2 makes it O(min(n, m)).

A single array also works if you save the upper-left value in a variable before overwriting each cell, but the two-row version is easier to get right and the asymptotic space is the same.

Edge cases and pitfalls