☕ DSA Java Articles

Topics › Dynamic Programming › DP on Strings

Print Longest Common Subsequence - (DP - 26)

Hard TUF ID 2799 A2Z

Java source ↗ Edit this article ↗

Problem

Given two strings s1 and s2, return a longest common subsequence itself, not just its length. A common subsequence is a string obtainable from both s1 and s2 by deleting characters without reordering the rest. When several longest ones exist, any of them is accepted. If the strings share no character, return the empty string.

Constraints: 1 ≤ n, m ≤ 1000 in the usual version; the Java methods also accept empty strings.

Example 1

s1 = "abcde", s2 = "ace"
answer = "ace"

Example 2

s1 = "abaaa", s2 = "baabaca"
answer = "baaa"     // "abaa" is equally long and also correct

The idea in one line

Compute the usual LCS length table, then start at the bottom-right cell and ask, at every step, which choice produced this value. Each time the answer is “the two characters matched”, that character belongs to the subsequence. The rest of this article builds up to that, then shows how to do the same in linear memory.

Recall the length recurrence on prefix lengths (f(i, j) = LCS length of s1[0..i) and s2[0..j)):

f(0, j) = f(i, 0) = 0
f(i, j) = 1 + f(i - 1, j - 1)                  if s1[i - 1] == s2[j - 1]
f(i, j) = max(f(i - 1, j), f(i, j - 1))        otherwise

When the last characters match, some LCS pairs them together; when they differ, at least one of them is unused and can be dropped. Both facts are proved in Longest common subsequence.

Approach 1: Brute force, recursion returning strings

Intuition. Make the recursion return the subsequence instead of its length. On a match, solve the smaller prefixes and append the matched character. On a mismatch, solve both “drop one character” subproblems and keep the longer string. On a tie it keeps the “drop from s2” branch; this rule is chosen so that the result is identical to Approach 2’s walk.

Algorithm.

  1. If either prefix is empty, return "".
  2. If the last characters match, return build(i - 1, j - 1) + s1[i - 1].
  3. Otherwise compute up = build(i - 1, j) and left = build(i, j - 1) and return the longer, preferring left on ties.
static String bruteForce(String s1, String s2) {
    return build(s1.length(), s2.length(), s1, s2);
}

/** One LCS of the prefixes s1[0..i) and s2[0..j). Ties go to the "drop from s2" branch. */
static String build(int i, int j, String s1, String s2) {
    if (i == 0 || j == 0) return "";
    if (s1.charAt(i - 1) == s2.charAt(j - 1)) return build(i - 1, j - 1, s1, s2) + s1.charAt(i - 1);
    String up = build(i - 1, j, s1, s2);                     // drop s1's last character
    String left = build(i, j - 1, s1, s2);                   // drop s2's last character
    return up.length() > left.length() ? up : left;
}

Complexity. Time exponential, O(2^(n + m)) calls in the worst case, and each call may also build a string of length up to min(n, m). Space O(n + m) stack plus the strings in flight. Memoizing strings would make it polynomial, but every cell would then store a string, O(n · m · min(n, m)) characters in total, which is why the standard method stores only lengths.

Approach 2: Tabulation, then walk back

Intuition. The table dp[i][j] of lengths already encodes every decision. Start at (n, m) and retrace:

Each step moves up, left, or diagonally, so the walk ends after at most n + m steps at row 0 or column 0. The characters are found from the back, so they are written into a char[] of length dp[n][m] from its last slot to its first, which avoids reversing at the end.

Taking the diagonal on a match, even when a neighbour has the same value, is always safe: the recurrence says a match gives dp[i][j] = 1 + dp[i - 1][j - 1], so following the diagonal keeps us on an optimal path.

Algorithm.

  1. Fill dp[n + 1][m + 1] exactly as in the LCS length problem.
  2. Set i = n, j = m, k = dp[n][m] - 1.
  3. While i > 0 and j > 0: on a match write s1[i - 1] at out[k--] and step diagonally; otherwise step toward the larger of up and left.
  4. Return new String(out).
static String tabulation(String s1, String s2) {
    int n = s1.length(), m = s2.length();
    int[][] dp = new int[n + 1][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)) dp[i][j] = 1 + dp[i - 1][j - 1];
            else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    char[] out = new char[dp[n][m]];
    int k = out.length - 1, i = n, j = m;
    while (i > 0 && j > 0) {
        if (s1.charAt(i - 1) == s2.charAt(j - 1)) {          // this character is part of the LCS
            out[k--] = s1.charAt(i - 1);
            i--;
            j--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            i--;                                             // the answer came from the cell above
        } else {
            j--;                                             // the answer came from the cell on the left
        }
    }
    return new String(out);
}

Dry run on Example 1, s1 = "abcde" (rows), s2 = "ace" (columns):

  ”” 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
at (i, j) characters move out
(5, 3) e = e diagonal __e
(4, 2) d ≠ c, up 2 > left 1 up __e
(3, 2) c = c diagonal _ce
(2, 1) b ≠ a, up 1 > left 0 up _ce
(1, 1) a = a diagonal ace

The walk stops at (0, 0) and returns "ace".

Complexity. Time O(n · m) to fill the table plus O(n + m) for the walk. Space O(n · m) for the table. This is the expected interview answer.

Approach 3: Linear space (Hirschberg)

Intuition. The length alone needs only two rows, but the walk back needs the whole table: for two strings of length 10^4 that is 10^8 ints, about 400 MB. Hirschberg’s algorithm recovers the subsequence with only O(n + m) extra memory by dividing and conquering.

Cut s1 in half at mid. Any LCS of the whole problem uses some characters of the top half of s1 matched inside a prefix s2[0..k), and the rest from the bottom half matched inside the suffix s2[k..m), for some split point k. So:

The recursion stops when a piece of s1 has one character: its LCS with a piece of s2 is that character if the piece contains it, otherwise empty.

Algorithm.

  1. split(a range, b range): return if either range is empty; handle a single character of a directly.
  2. Otherwise compute cut with bestCut (one forward and one backward row), then recurse on the left parts and then on the right parts, appending to one shared StringBuilder.
static String linearSpace(String s1, String s2) {
    StringBuilder out = new StringBuilder();
    split(s1, 0, s1.length(), s2, 0, s2.length(), out);
    return out.toString();
}

/** Appends one LCS of a[aLo..aHi) and b[bLo..bHi) to out. */
static void split(String a, int aLo, int aHi, String b, int bLo, int bHi, StringBuilder out) {
    if (aLo >= aHi || bLo >= bHi) return;
    if (aHi - aLo == 1) {                                    // one character of a: it is the LCS if b contains it
        for (int k = bLo; k < bHi; k++) {
            if (b.charAt(k) == a.charAt(aLo)) {
                out.append(a.charAt(aLo));
                return;
            }
        }
        return;
    }
    int mid = (aLo + aHi) / 2;
    int cut = bestCut(a, aLo, mid, aHi, b, bLo, bHi);
    split(a, aLo, mid, b, bLo, cut, out);                    // LCS = (LCS of the top half) + (LCS of the bottom half)
    split(a, mid, aHi, b, cut, bHi, out);
}

/** Where an optimal alignment crosses from a[aLo..mid) into a[mid..aHi): the split point in b. */
static int bestCut(String a, int aLo, int mid, int aHi, String b, int bLo, int bHi) {
    int[] top = forwardRow(a, aLo, mid, b, bLo, bHi);       // top[k] = LCS(a[aLo..mid), first k chars of b)
    int[] bottom = backwardRow(a, mid, aHi, b, bLo, bHi);   // bottom[k] = LCS(a[mid..aHi), last k chars of b)
    int w = bHi - bLo, best = 0;
    for (int k = 1; k <= w; k++) {
        if (top[k] + bottom[w - k] > top[best] + bottom[w - best]) best = k;
    }
    return bLo + best;
}

/** Last row of the LCS table of a[aLo..aHi) against prefixes of b[bLo..bHi), using two rows. */
static int[] forwardRow(String a, int aLo, int aHi, String b, int bLo, int bHi) {
    int w = bHi - bLo;
    int[] prev = new int[w + 1], cur = new int[w + 1];
    for (int i = aLo; i < aHi; i++) {
        for (int k = 1; k <= w; k++) {
            if (a.charAt(i) == b.charAt(bLo + k - 1)) cur[k] = 1 + prev[k - 1];
            else cur[k] = Math.max(prev[k], cur[k - 1]);
        }
        int[] tmp = prev; prev = cur; cur = tmp;
    }
    return prev;
}

/** The same scan run from the right ends: row[k] = LCS(a[aLo..aHi), last k chars of b[bLo..bHi)). */
static int[] backwardRow(String a, int aLo, int aHi, String b, int bLo, int bHi) {
    int w = bHi - bLo;
    int[] prev = new int[w + 1], cur = new int[w + 1];
    for (int i = aHi - 1; i >= aLo; i--) {
        for (int k = 1; k <= w; k++) {
            if (a.charAt(i) == b.charAt(bHi - k)) cur[k] = 1 + prev[k - 1];
            else cur[k] = Math.max(prev[k], cur[k - 1]);
        }
        int[] tmp = prev; prev = cur; cur = tmp;
    }
    return prev;
}

Complexity. Time O(n · m): the top level scans n × m cells, the next level scans n/2 rows against pieces of s2 whose widths add up to m, and so on, for a total of at most 2 · n · m. Space O(n + m): the two rows are freed when bestCut returns, the recursion is O(log n) deep, and the output has at most min(n, m) characters.

It may return a different LCS from Approach 2 when several exist, since it breaks ties by split point. The tests therefore check that every result is a common subsequence of the right length, and compare exact strings only where the LCS is unique.

Edge cases and pitfalls