Print Longest Common Subsequence

Medium20–25 min

Topics

Dynamic ProgrammingString

Companies

AmazonMicrosoftAdobe

Given two strings, reconstruct one actual longest common subsequence rather than just its length — the longest sequence of characters that appears in both strings in the same relative order, though not necessarily touching. When the two strings share nothing this way, the reconstructed answer is the empty string. Since more than one longest common subsequence can exist for the same pair of strings, ties are broken by preferring to skip a character of the first string over the second whenever both directions are equally good, so the result stays deterministic. The same length-only table used to compute how long the common subsequence is also records enough information to rebuild it: a cell reached because both tail characters matched must have that character in the answer, and a cell reached because one string's tail character was dropped points toward whichever neighbor produced its value. Walking that table backward from the final cell — either through recursive calls that unwind in the correct order, or through an explicit loop whose output gets reversed at the end — replays exactly the choices that were made while filling it, turning the stored lengths back into one concrete subsequence.

Test Case 1:

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

Output:"ace"

Explanation:Walking backward from the end of both strings, 'e' matches first, then 'c', then 'a' — read forward that spells "ace", the full length-3 subsequence.

Test Case 2:

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

Output:""

Explanation:No character is shared, so the reconstructed subsequence is empty.

Test Case 3:

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

Output:""

Explanation:One string is empty, so there is nothing to trace back through — the result is the empty string.

Constraints

◆0 ≤ text1.length, text2.length ≤ 12
◆text1 and text2 consist only of lowercase English letters
◆If more than one longest common subsequence exists, return the one produced by preferring to move up (skip a character of text1) over moving left whenever both directions tie

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Recursive Backtrack After Building the DP Table

Optimal

First fill the same length-only dp[i][j] table used for the length variant of this problem: for every prefix pair, either extend the diagonal on a matching tail character or carry forward the better of the two neighboring prefixes. Once the table is complete, walk it backward from the bottom-right corner with a small recursive helper. A matching tail character is always part of the answer, so the helper recurses one step closer to the base case and appends that character only after the recursive call returns — which naturally places every matched character in the correct left-to-right order. When the tail characters differ, the helper follows whichever neighboring cell holds the larger value, preferring the cell above when both are equal.

TimeO(n·m)

SpaceO(n·m)

Java

Try it out

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

    private String backtrack(int[][] dp, String text1, String text2, int i, int j) {
        if (i == 0 || j == 0) return "";
        if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
            return backtrack(dp, text1, text2, i - 1, j - 1) + text1.charAt(i - 1);
        }
        if (dp[i - 1][j] >= dp[i][j - 1]) {
            return backtrack(dp, text1, text2, i - 1, j);
        }
        return backtrack(dp, text1, text2, i, j - 1);
    }
}

Iterative Backtrack After Building the DP Table

Optimal

Build the exact same dp[i][j] length table bottom-up. Then, instead of recursing, walk it with a simple loop: start two pointers at the bottom-right corner and step through the table one cell at a time. A matching tail character gets collected and both pointers move diagonally inward; otherwise the pointer moves toward whichever neighboring cell holds the larger value, favoring the upward move on a tie. Because this walk visits characters from the end of the subsequence toward its start, the collected characters come out backward and are reversed once at the end before being returned.

TimeO(n·m)

SpaceO(n·m)

Java

Try it out

class Solution {
    public String printLCS(String text1, String text2) {
        int n = text1.length(), m = text2.length();
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        int i = n, j = m;
        while (i > 0 && j > 0) {
            if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                sb.append(text1.charAt(i - 1));
                i--;
                j--;
            } else if (dp[i - 1][j] >= dp[i][j - 1]) {
                i--;
            } else {
                j--;
            }
        }
        return sb.reverse().toString();
    }
}

Print Longest Common Subsequence

Constraints

Try the Dry Run

Approach & Solutions

Recursive Backtrack After Building the DP Table

Iterative Backtrack After Building the DP Table

Related Problems