☕ DSA Java Articles

Topics › Dynamic Programming › DP on Strings

Shortest common supersequence

Hard TUF ID 313 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Given two strings s1 and s2, return the shortest string that contains both of them as subsequences. If there are several shortest strings, any one of them is accepted.

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

Example 1

s1 = "abac", s2 = "cab"
answer = "cabac"     // drop the first 'c' -> "abac"; drop the last "ac" -> "cab"

Example 2

s1 = "brute", s2 = "groot"
answer = "bgruoote"  // length 8 = 5 + 5 - 2, the shared "rt" is written once

Key insight: write the shared part once

Concatenating the strings always works but wastes space. Each character of a supersequence serves s1, s2, or both. The characters that serve both appear in the same order in both strings, so they form a common subsequence. The more of them there are, the shorter the result:

length = n + m - (number of shared characters) ≥ n + m - LCS

and the bound is reached by sharing a Longest common subsequence. For Example 2, the LCS of "brute" and "groot" is "rt", so the answer has length 5 + 5 - 2 = 8.

To build the string itself, merge the two strings along an LCS: write every LCS character once, and before each one, write the characters of s1 and s2 that lie between it and the previous LCS character.

Approach 1: Brute force, recursion returning strings

Intuition. Work on prefixes s1[0..i) and s2[0..j) and decide the last character of the supersequence:

Algorithm.

  1. If i == 0 return s2[0..j); if j == 0 return s1[0..i).
  2. On a match return build(i - 1, j - 1) + s1[i - 1].
  3. Otherwise compare build(i - 1, j) + s1[i - 1] with build(i, j - 1) + s2[j - 1] and return the shorter.
static String bruteForce(String s1, String s2) {
    return build(s1.length(), s2.length(), s1, s2);
}

/** A shortest common supersequence of s1[0..i) and s2[0..j). Ties go to "s2's last character goes last". */
static String build(int i, int j, String s1, String s2) {
    if (i == 0) return s2.substring(0, j);                   // nothing left of s1: the rest of s2 is needed as is
    if (j == 0) return s1.substring(0, i);
    if (s1.charAt(i - 1) == s2.charAt(j - 1)) return build(i - 1, j - 1, s1, s2) + s1.charAt(i - 1);  // one copy serves both
    String up = build(i - 1, j, s1, s2) + s1.charAt(i - 1);  // s1's last character ends the answer
    String left = build(i, j - 1, s1, s2) + s2.charAt(j - 1);// s2's last character ends the answer
    return up.length() < left.length() ? up : left;
}

Complexity. Time exponential, about O(2^(n + m)) calls, each building a string of length up to n + m. Space O(n + m) stack plus the strings in flight. Useful only to check the fast method on small inputs.

Approach 2: Optimal, LCS table and walk back

Intuition. Build the LCS length table, then start from (n, m) and retrace the decisions, writing characters as you go (back to front):

Compared with printing the LCS, the only differences are that unmatched characters are written instead of skipped, and the leftover prefix is appended at the end. Reverse the builder once at the end.

Algorithm.

  1. Fill dp[n + 1][m + 1] with LCS lengths.
  2. Walk from (n, m) while i > 0 and j > 0, appending as described.
  3. Append the rest of s1[0..i) and s2[0..j) (one of them is empty).
  4. Reverse and return.
static String optimal(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]);
        }
    }
    StringBuilder sb = new StringBuilder();                  // built backwards, reversed at the end
    int i = n, j = m;
    while (i > 0 && j > 0) {
        if (s1.charAt(i - 1) == s2.charAt(j - 1)) {          // an LCS character: write it once for both strings
            sb.append(s1.charAt(i - 1));
            i--;
            j--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            sb.append(s1.charAt(i - 1));                     // s1's character is not shared: write it alone
            i--;
        } else {
            sb.append(s2.charAt(j - 1));
            j--;
        }
    }
    while (i > 0) sb.append(s1.charAt(--i));                 // whatever is left of either string
    while (j > 0) sb.append(s2.charAt(--j));
    return sb.reverse().toString();
}

Dry run on Example 2, s1 = "brute" (rows), s2 = "groot" (columns). The LCS table:

  ”” g r o o t
”” 0 0 0 0 0 0
b 0 0 0 0 0 0
r 0 0 1 1 1 1
u 0 0 1 1 1 1
t 0 0 1 1 1 2
e 0 0 1 1 1 2
at (i, j) compare move written
(5, 5) e ≠ t, up 2 > left 1 up e
(4, 5) t = t diagonal t
(3, 4) u ≠ o, tie 1 = 1 left o
(3, 3) u ≠ o, tie 1 = 1 left o
(3, 2) u ≠ r, up 1 > left 0 up u
(2, 2) r = r diagonal r
(1, 1) b ≠ g, tie 0 = 0 left g
(1, 0) s2 used up leftover b

Written back to front: e t o o u r g b. Reversed: "bgruoote", length 8.

Complexity. Time O(n · m) for the table plus O(n + m) for the walk. Space O(n · m) for the table.

Length only

If only the length is needed, there is no walk, so two LCS rows suffice and the answer is n + m - LCS. The tests use this method to confirm the length of every string the other two return.

static int shortestLength(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;
    }
    return n + m - prev[m];
}

Complexity. Time O(n · m), space O(m). Recovering the string itself in linear space is possible with Hirschberg’s divide and conquer, shown in Print Longest Common Subsequence - (DP - 26).

Edge cases and pitfalls