Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Shortest Common Supersequence

HARDProblemSolveExternal Links

Description

Given two strings str1 and str2, return the shortest string that has both str1 and str2 as subsequences. If there are multiple valid answers, return any of them.

A subsequence of a string is a sequence that can be derived from the string by deleting zero or more characters without changing the relative order of the remaining characters. For example, "ace" is a subsequence of "abcde".

A supersequence is a string that contains both input strings as subsequences. We want to find the shortest such string — the one that merges both strings with as much overlap as possible.

Examples

Example 1

Input: str1 = "abac", str2 = "cab"

Output: "cabac"

Explanation:

  • str1 = "abac" is a subsequence of "cabac" — delete the first 'c' to get "abac".
  • str2 = "cab" is a subsequence of "cabac" — delete the last 'a' and 'c' to get "cab".
  • The result has length 5, which is the shortest possible. The common subsequence "ab" is shared and appears only once in the supersequence.

Example 2

Input: str1 = "aaaaaaaa", str2 = "aaaaaaaa"

Output: "aaaaaaaa"

Explanation: Both strings are identical. The shortest supersequence is just the string itself, since it trivially contains both as subsequences. When both strings are the same, the LCS equals the entire string, so the SCS equals the string.

Constraints

  • 1 ≤ str1.length, str2.length ≤ 1000
  • str1 and str2 consist of lowercase English letters.

Editorial

Brute Force

Intuition

Imagine you are trying to merge two playlists into the shortest combined playlist that preserves the order of songs in each original list. When both playlists have the same next song, you only need to add it once. When they differ, you have to pick one — but which one leads to the shorter combined list?

This is exactly our problem. We compare the strings from the end:

  • If the last characters match: That character belongs in the supersequence exactly once. Include it and recurse on both strings with one character removed from each.
  • If the last characters differ: We have two choices — include the last character of str1 (and recurse without it) or include the last character of str2 (and recurse without it). We try both and pick whichever gives the shorter result.
  • If one string is empty: The supersequence must include all remaining characters of the other string.

This brute force explores all possible ways to merge the two strings, which results in an exponential number of recursive calls.

Step-by-Step Explanation

Let's trace through with str1 = "abac", str2 = "cab".

Step 1: Call solve(4, 3). Compare str1[3]='c' with str2[2]='b'. They don't match. We must try both options:

  • Option A: Include 'c' from str1 → solve(3, 3)
  • Option B: Include 'b' from str2 → solve(4, 2)

Step 2: Explore Option A — solve(3, 3). Compare str1[2]='a' with str2[2]='b'. No match. Branch into solve(2, 3) and solve(3, 2).

Step 3: Explore solve(2, 3). Compare str1[1]='b' with str2[2]='b'. Match! Include 'b' once and recurse to solve(1, 2).

Step 4: solve(1, 2). Compare str1[0]='a' with str2[1]='a'. Match! Include 'a' once and recurse to solve(0, 1).

Step 5: solve(0, 1). Base case: str1 is exhausted (m=0). Return remaining str2 characters = "c". Length = 1.

Step 6: Unwind: solve(1,2) = 1 + 1 = 2 characters. solve(2,3) = 1 + 2 = 3. Now explore solve(3, 2).

Step 7: solve(3, 2). Compare str1[2]='a' with str2[1]='a'. Match! → solve(2, 1). After resolving: solve(3,2) = 4.

Step 8: Resolve solve(3, 3) = 1 + min(3, 4) = 4 characters.

Step 9: Explore Option B — solve(4, 2). This requires solve(3, 2) which was already computed as 4 in Step 7 — an overlapping subproblem! The brute force recomputes it from scratch.

Step 10: After resolving: solve(4, 2) = 5.

Step 11: Final: solve(4, 3) = 1 + min(4, 5) = 5. The shortest common supersequence has length 5.

Notice solve(3,2) was computed twice. For larger strings, this overlap grows exponentially.

Recursive Exploration of Merging Choices — Watch how the recursion branches at each mismatch and collapses back. Notice solve(3,2) is computed twice — an overlapping subproblem that causes exponential blowup.

Algorithm

  1. Define solve(m, n) = length of shortest common supersequence of str1[0..m-1] and str2[0..n-1].
  2. Base cases: If m == 0, return n (append all of str2). If n == 0, return m (append all of str1).
  3. Match: If str1[m-1] == str2[n-1], return 1 + solve(m-1, n-1) — include the character once.
  4. Mismatch: Return 1 + min(solve(m-1, n), solve(m, n-1)) — try including either character.
  5. The answer is solve(len(str1), len(str2)).

Note: This only computes the length. To construct the actual string, we need the full DP table (see next approach).

Code

class Solution {
public:
    string shortestCommonSupersequence(string str1, string str2) {
        // Brute force: recursive length computation
        // Cannot efficiently construct the string without DP table
        // Shown for educational purposes to illustrate the recursion
        return solve(str1, str2, str1.size(), str2.size());
    }

private:
    string solve(string& s1, string& s2, int m, int n) {
        if (m == 0) return s2.substr(0, n);
        if (n == 0) return s1.substr(0, m);

        if (s1[m - 1] == s2[n - 1]) {
            return solve(s1, s2, m - 1, n - 1) + s1[m - 1];
        }

        string opt1 = solve(s1, s2, m - 1, n) + s1[m - 1];
        string opt2 = solve(s1, s2, m, n - 1) + s2[n - 1];
        return opt1.size() <= opt2.size() ? opt1 : opt2;
    }
};
class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        def solve(m: int, n: int) -> str:
            if m == 0:
                return str2[:n]
            if n == 0:
                return str1[:m]

            if str1[m - 1] == str2[n - 1]:
                return solve(m - 1, n - 1) + str1[m - 1]

            opt1 = solve(m - 1, n) + str1[m - 1]
            opt2 = solve(m, n - 1) + str2[n - 1]
            return opt1 if len(opt1) <= len(opt2) else opt2

        return solve(len(str1), len(str2))
class Solution {
    public String shortestCommonSupersequence(String str1, String str2) {
        return solve(str1, str2, str1.length(), str2.length());
    }

    private String solve(String s1, String s2, int m, int n) {
        if (m == 0) return s2.substring(0, n);
        if (n == 0) return s1.substring(0, m);

        if (s1.charAt(m - 1) == s2.charAt(n - 1)) {
            return solve(s1, s2, m - 1, n - 1) + s1.charAt(m - 1);
        }

        String opt1 = solve(s1, s2, m - 1, n) + s1.charAt(m - 1);
        String opt2 = solve(s1, s2, m, n - 1) + s2.charAt(n - 1);
        return opt1.length() <= opt2.length() ? opt1 : opt2;
    }
}

Complexity Analysis

Time Complexity: O(2^(m+n))

At each mismatch, the recursion branches into two calls, each reducing the problem size by 1. In the worst case, the recursion tree has depth m+n and branches at nearly every level. Combined with string construction at each step (creating temporary strings), this is extremely slow.

Space Complexity: O((m+n) · 2^(m+n))

The recursion stack depth is O(m+n). Additionally, at each call we create temporary strings of length up to m+n. The total space for all temporary strings across all recursive branches is exponential.

Why This Approach Is Not Efficient

The brute force has O(2^(m+n)) time complexity. With m and n up to 1000, that's 2^2000 operations — unimaginably large.

The root cause is overlapping subproblems. The recursion tree computes the same (m, n) pairs repeatedly. In our trace, solve(3,2) was computed twice. For longer strings, the same subproblem can be recomputed thousands or millions of times.

Since the subproblems are defined by just two integers (i, j) where 0 ≤ i ≤ m and 0 ≤ j ≤ n, there are only O(m·n) unique subproblems. By storing results in a 2D table, we can compute each subproblem exactly once and use the table to construct the actual supersequence string by backtracking.

Better Approach - Direct SCS Dynamic Programming

Intuition

We turn the recursive approach into an iterative one by building a 2D table dp[i][j] representing the length of the shortest common supersequence of str1[0..i-1] and str2[0..j-1].

The key rules are the same as the recursion:

  • Base cases: dp[i][0] = i (if str2 is empty, take all of str1) and dp[0][j] = j (if str1 is empty, take all of str2).
  • Match: If str1[i-1] == str2[j-1], then dp[i][j] = 1 + dp[i-1][j-1] — include the character once.
  • Mismatch: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1]) — take the shorter option.

Once the table is filled, we backtrack from dp[m][n] to dp[0][0] to reconstruct the actual shortest string. At each cell, we reverse the decision we made: if characters matched, include it once and go diagonally; if not, follow the direction of the smaller value.

Step-by-Step Explanation

Let's trace with str1 = "abac", str2 = "cab".

Phase 1: Fill the SCS Table

Step 1: Initialize borders: dp[i][0] = i for i=0..4 and dp[0][j] = j for j=0..3.

Step 2: dp[1][1]: str1[0]='a' ≠ str2[0]='c' → 1 + min(dp[0][1], dp[1][0]) = 1 + min(1,1) = 2.

Step 3: dp[1][2]: str1[0]='a' == str2[1]='a' → Match! 1 + dp[0][1] = 1 + 1 = 2.

Step 4: dp[2][3]: str1[1]='b' == str2[2]='b' → Match! 1 + dp[1][2] = 1 + 2 = 3.

Step 5: dp[4][1]: str1[3]='c' == str2[0]='c' → Match! 1 + dp[3][0] = 1 + 3 = 4.

Step 6: dp[4][3]: str1[3]='c' ≠ str2[2]='b' → 1 + min(dp[3][3], dp[4][2]) = 1 + min(4, 5) = 5.

Final table:

       ""  c  a  b
""   [ 0  1  2  3 ]
a    [ 1  2  2  3 ]
b    [ 2  3  3  3 ]
a    [ 3  4  4  4 ]
c    [ 4  4  5  5 ]

Phase 2: Backtrack to Construct the String

Step 7: Start at (4,3). str1[3]='c' ≠ str2[2]='b'. dp[3][3]=4 < dp[4][2]=5 → go up. Include 'c'.

Step 8: At (3,3). str1[2]='a' ≠ str2[2]='b'. dp[2][3]=3 < dp[3][2]=4 → go up. Include 'a'.

Step 9: At (2,3). str1[1]='b' == str2[2]='b' → Match! Include 'b' once. Go diagonal to (1,2).

Step 10: At (1,2). str1[0]='a' == str2[1]='a' → Match! Include 'a' once. Go diagonal to (0,1).

Step 11: At (0,1). i=0, str1 exhausted. Add remaining str2[0]='c'.

Built in reverse: ['c', 'a', 'b', 'a', 'c'] → Reversed: "cabac" ✓

Direct SCS Table Fill + Backtracking to Construct String — Watch the SCS table fill cell by cell, then see the backtracking path that constructs the actual shortest supersequence string character by character.

Algorithm

Phase 1: Build the SCS Length Table

  1. Create a 2D table dp of size (m+1) × (n+1).
  2. Initialize: dp[i][0] = i and dp[0][j] = j.
  3. Fill row by row:
    • If str1[i-1] == str2[j-1]: dp[i][j] = 1 + dp[i-1][j-1].
    • Else: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1]).

Phase 2: Backtrack to Construct the String
4. Start at (m, n). Initialize an empty result list.
5. While both i > 0 and j > 0:

  • If str1[i-1] == str2[j-1]: append the character, move diagonally (i-1, j-1).
  • Else if dp[i-1][j] < dp[i][j-1]: append str1[i-1], move up (i-1, j).
  • Else: append str2[j-1], move left (i, j-1).
  1. Append remaining characters of whichever string is not exhausted.
  2. Reverse the result list to get the SCS.

Code

class Solution {
public:
    string shortestCommonSupersequence(string str1, string str2) {
        int m = str1.size(), n = str2.size();

        // Phase 1: Build SCS length table
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for (int i = 0; i <= m; i++) dp[i][0] = i;
        for (int j = 0; j <= n; j++) dp[0][j] = j;

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (str1[i - 1] == str2[j - 1]) {
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                } else {
                    dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        // Phase 2: Backtrack to construct SCS
        string result;
        int i = m, j = n;
        while (i > 0 && j > 0) {
            if (str1[i - 1] == str2[j - 1]) {
                result += str1[i - 1];
                i--; j--;
            } else if (dp[i - 1][j] < dp[i][j - 1]) {
                result += str1[i - 1];
                i--;
            } else {
                result += str2[j - 1];
                j--;
            }
        }
        while (i > 0) { result += str1[i - 1]; i--; }
        while (j > 0) { result += str2[j - 1]; j--; }

        reverse(result.begin(), result.end());
        return result;
    }
};
class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        m, n = len(str1), len(str2)

        # Phase 1: Build SCS length table
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(m + 1):
            dp[i][0] = i
        for j in range(n + 1):
            dp[0][j] = j

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if str1[i - 1] == str2[j - 1]:
                    dp[i][j] = 1 + dp[i - 1][j - 1]
                else:
                    dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1])

        # Phase 2: Backtrack to construct SCS
        result = []
        i, j = m, n
        while i > 0 and j > 0:
            if str1[i - 1] == str2[j - 1]:
                result.append(str1[i - 1])
                i -= 1
                j -= 1
            elif dp[i - 1][j] < dp[i][j - 1]:
                result.append(str1[i - 1])
                i -= 1
            else:
                result.append(str2[j - 1])
                j -= 1

        while i > 0:
            result.append(str1[i - 1])
            i -= 1
        while j > 0:
            result.append(str2[j - 1])
            j -= 1

        return ''.join(reversed(result))
class Solution {
    public String shortestCommonSupersequence(String str1, String str2) {
        int m = str1.length(), n = str2.length();

        // Phase 1: Build SCS length table
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) dp[i][0] = i;
        for (int j = 0; j <= n; j++) dp[0][j] = j;

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                } else {
                    dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        // Phase 2: Backtrack to construct SCS
        StringBuilder result = new StringBuilder();
        int i = m, j = n;
        while (i > 0 && j > 0) {
            if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                result.append(str1.charAt(i - 1));
                i--; j--;
            } else if (dp[i - 1][j] < dp[i][j - 1]) {
                result.append(str1.charAt(i - 1));
                i--;
            } else {
                result.append(str2.charAt(j - 1));
                j--;
            }
        }
        while (i > 0) { result.append(str1.charAt(i - 1)); i--; }
        while (j > 0) { result.append(str2.charAt(j - 1)); j--; }

        return result.reverse().toString();
    }
}

Complexity Analysis

Time Complexity: O(m × n)

Filling the 2D table requires visiting each of the (m+1) × (n+1) cells once, each in O(1) time. The backtracking phase takes at most O(m + n) steps. Total: O(m × n).

Space Complexity: O(m × n)

The 2D DP table has (m+1) × (n+1) entries. The backtracking requires the full table to be available (we can't space-optimize to 1D because backtracking needs to look at cells from all rows). For m = n = 1000, this is about 1 million entries — feasible.

Why This Approach Is Not Efficient

The direct SCS DP approach runs in O(m × n) time with O(m × n) space, which is practical and passes the constraints. However, it requires defining and understanding a custom DP recurrence specific to the SCS problem.

There is a more elegant approach that reduces SCS to the well-known Longest Common Subsequence (LCS) problem. The key insight is:

SCS length = len(str1) + len(str2) − LCS length

Why? The LCS represents characters shared between both strings (in the same order). In the shortest supersequence, these shared characters appear only once instead of twice. So we save exactly LCS characters from the naive concatenation str1 + str2.

The LCS-based approach is preferred because:

  1. LCS is a fundamental, widely-known algorithm — solving SCS via LCS builds on existing knowledge.
  2. The backtracking through an LCS table to construct the SCS is clean and systematic.
  3. It clearly separates the problem into two well-defined phases: find what's common (LCS), then merge the rest.

Optimal Approach - LCS-Based Construction

Intuition

The idea is beautifully simple: to find the shortest common supersequence, first find the longest common subsequence (LCS) of the two strings. The LCS tells us which characters are shared between both strings in the same order.

Once we know the LCS, we can construct the SCS by interleaving the two strings, including shared (LCS) characters only once:

  1. Build the LCS table using standard DP.
  2. Backtrack through the LCS table starting from the bottom-right corner:
    • If characters match (they're part of the LCS): include the character once and move diagonally.
    • If they don't match: include the character from whichever direction the LCS value came from, and move in that direction.
  3. When one string is exhausted, append the remaining characters of the other.

For str1 = "abac" and str2 = "cab", the LCS is "ab" (length 2). The SCS length = 4 + 3 − 2 = 5. The backtracking produces "cabac".

This approach has the same time and space complexity as the direct approach, but it's conceptually cleaner because it separates the problem into "find what's common" (LCS) and "merge everything" (backtracking).

Diagram showing how the LCS of str1=abac and str2=cab is used to construct the shortest common supersequence cabac
Diagram showing how the LCS of str1=abac and str2=cab is used to construct the shortest common supersequence cabac

Step-by-Step Explanation

Let's trace with str1 = "abac", str2 = "cab".

Phase 1: Build the LCS Table

Step 1: Initialize: first row and column are all 0.

Step 2: dp[1][2]: str1[0]='a' == str2[1]='a' → dp[0][1] + 1 = 1. First LCS match!

Step 3: dp[2][3]: str1[1]='b' == str2[2]='b' → dp[1][2] + 1 = 2. LCS grows to 2!

Step 4: dp[4][1]: str1[3]='c' == str2[0]='c' → dp[3][0] + 1 = 1.

Step 5: Complete table:

       ""  c  a  b
""   [ 0  0  0  0 ]
a    [ 0  0  1  1 ]
b    [ 0  0  1  2 ]
a    [ 0  0  1  2 ]
c    [ 0  1  1  2 ]

LCS = 2. The LCS is "ab". SCS length = 4 + 3 − 2 = 5.

Phase 2: Backtrack to Construct SCS

Step 6: Start at (4,3). str1[3]='c' ≠ str2[2]='b'. dp[3][3]=2 vs dp[4][2]=1. dp[3][3] > dp[4][2] → LCS came from above. Include str1[3]='c', go up.

Step 7: At (3,3). str1[2]='a' ≠ str2[2]='b'. dp[2][3]=2 vs dp[3][2]=1. dp[2][3] > dp[3][2] → go up. Include str1[2]='a'.

Step 8: At (2,3). str1[1]='b' == str2[2]='b' → Match (LCS character)! Include 'b' once, go diagonal to (1,2).

Step 9: At (1,2). str1[0]='a' == str2[1]='a' → Match (LCS character)! Include 'a' once, go diagonal to (0,1).

Step 10: At (0,1). i=0, str1 exhausted. Add remaining str2: str2[0]='c'.

Built in reverse: ['c', 'a', 'b', 'a', 'c'] → Reversed: "cabac" ✓

LCS Table + Backtracking to Build Shortest Common Supersequence — Watch the LCS table fill to find common characters, then see how backtracking constructs the SCS by weaving both strings together, sharing LCS characters.

Algorithm

Phase 1: Build the LCS Table

  1. Create a 2D table dp of size (m+1) × (n+1), initialized to 0.
  2. Fill row by row using the standard LCS recurrence:
    • If str1[i-1] == str2[j-1]: dp[i][j] = dp[i-1][j-1] + 1.
    • Else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

Phase 2: Backtrack Through LCS Table to Build SCS
3. Start at (m, n). Initialize an empty result list.
4. While both i > 0 and j > 0:

  • If str1[i-1] == str2[j-1]: this is an LCS character. Include it once, move diagonally (i-1, j-1).
  • Else if dp[i-1][j] > dp[i][j-1]: the LCS came from above. Include str1[i-1], move up (i-1, j).
  • Else: the LCS came from the left. Include str2[j-1], move left (i, j-1).
  1. Append remaining characters of whichever string is not exhausted.
  2. Reverse the result to get the SCS.

Key insight: The backtracking follows the LCS path. Characters ON the LCS path are included once (shared). Characters OFF the LCS path are included from their respective string.

Code

class Solution {
public:
    string shortestCommonSupersequence(string str1, string str2) {
        int m = str1.size(), n = str2.size();

        // Phase 1: Build LCS table
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (str1[i - 1] == str2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        // Phase 2: Backtrack to construct SCS
        string result;
        int i = m, j = n;
        while (i > 0 && j > 0) {
            if (str1[i - 1] == str2[j - 1]) {
                result += str1[i - 1];
                i--; j--;
            } else if (dp[i - 1][j] > dp[i][j - 1]) {
                result += str1[i - 1];
                i--;
            } else {
                result += str2[j - 1];
                j--;
            }
        }
        while (i > 0) { result += str1[i - 1]; i--; }
        while (j > 0) { result += str2[j - 1]; j--; }

        reverse(result.begin(), result.end());
        return result;
    }
};
class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        m, n = len(str1), len(str2)

        # Phase 1: Build LCS table
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if str1[i - 1] == str2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

        # Phase 2: Backtrack to construct SCS
        result = []
        i, j = m, n
        while i > 0 and j > 0:
            if str1[i - 1] == str2[j - 1]:
                result.append(str1[i - 1])
                i -= 1
                j -= 1
            elif dp[i - 1][j] > dp[i][j - 1]:
                result.append(str1[i - 1])
                i -= 1
            else:
                result.append(str2[j - 1])
                j -= 1

        while i > 0:
            result.append(str1[i - 1])
            i -= 1
        while j > 0:
            result.append(str2[j - 1])
            j -= 1

        return ''.join(reversed(result))
class Solution {
    public String shortestCommonSupersequence(String str1, String str2) {
        int m = str1.length(), n = str2.length();

        // Phase 1: Build LCS table
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (str1.charAt(i - 1) == str2.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]);
                }
            }
        }

        // Phase 2: Backtrack to construct SCS
        StringBuilder result = new StringBuilder();
        int i = m, j = n;
        while (i > 0 && j > 0) {
            if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                result.append(str1.charAt(i - 1));
                i--; j--;
            } else if (dp[i - 1][j] > dp[i][j - 1]) {
                result.append(str1.charAt(i - 1));
                i--;
            } else {
                result.append(str2.charAt(j - 1));
                j--;
            }
        }
        while (i > 0) { result.append(str1.charAt(i - 1)); i--; }
        while (j > 0) { result.append(str2.charAt(j - 1)); j--; }

        return result.reverse().toString();
    }
}

Complexity Analysis

Time Complexity: O(m × n)

Building the LCS table requires filling (m+1) × (n+1) cells, each in O(1). The backtracking phase visits at most m + n cells (moving up or left at each step). Total: O(m × n).

Space Complexity: O(m × n)

We need the full 2D LCS table for the backtracking phase. Unlike the length-only version where we could optimize to O(n) space with two rows, here we must keep the entire table because backtracking needs to navigate from (m, n) back to (0, 0), accessing cells from any row.

This is the optimal approach for this problem — the O(m × n) time is necessary because we must examine all character pairs to determine the LCS, and O(m × n) space is necessary because we need the full table for string construction.