Log inSign up
hardGeeksforGeeksNot Started

Shortest Common Supersequence

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Dynamic Programming
Solve on GeeksforGeeks
Lesson

Problem Statement

Given two strings str1 and str2, return the shortest string that has both str1 and str2 as subsequences.

If there are multiple valid shortest common supersequences, you may return any of them.

### Example 1 - Input: str1 = "abac", str2 = "cab" - Output: "cabac" - Explanation: - "abac" is a subsequence of "cabac" (indices 1, 2, 3, 4). - "cab" is a subsequence of "cabac" (indices 0, 1, 2). - The shortest length is 5.

### Example 2 - Input: str1 = "aaaaaaaa", str2 = "aaaaaaaa" - Output: "aaaaaaaa"

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the mathematical link between LCS and SCS.
  • Reconstruct full sequence answers via 2D DP matrix backtracking.
  • Handle remaining characters when one string is exhausted during backtracking.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Merging two strings into a minimal supersequence containing both.
  • String subsequence alignment.

Algorithmic Decision Tree:

  • Build full (m+1) x (n+1) LCS matrix.
  • Backtrack to reconstruct the answer string.

Connected Patterns:

Longest Common SubsequenceEdit DistanceDelete Operation for Two Strings

1. Recursive Character Interleaving

Intuition

Recursively try choosing characters from str1 or str2 to construct the shortest valid supersequence.

Algorithm

  1. Define solve(i, j).
  2. If i == m, return remaining of str2[j..].
  3. If j == n, return remaining of str1[i..].
  4. If str1[i] == str2[j], return str1[i] + solve(i + 1, j + 1).
  5. Option 1: str1[i] + solve(i + 1, j).
  6. Option 2: str2[j] + solve(i, j + 1).
  7. Return the option with smaller string length.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8 string solve(int i, int j, const string& s1, const string& s2) {
9 if (i == s1.length()) return s2.substr(j);
10 if (j == s2.length()) return s1.substr(i);
11
12 if (s1[i] == s2[j]) {
13 return s1[i] + solve(i + 1, j + 1, s1, s2);
14 }
15
16 string opt1 = s1[i] + solve(i + 1, j, s1, s2);
17 string opt2 = s2[j] + solve(i, j + 1, s1, s2);
18
19 return (opt1.length() <= opt2.length()) ? opt1 : opt2;
20 }
21public:
22 string shortestCommonSupersequence(string str1, string str2) {
23 return solve(0, 0, str1, str2);
24 }
25};
26
27int main() {
28 Solution sol;
29 cout << "SCS: " << sol.shortestCommonSupersequence("abac", "cab") << endl;
30 return 0;
31}

Time & Space Complexity

  • Time complexity: O(2^(m + n))
  • Space complexity: O(m + n)

2. Memoized LCS Length + String Backtracking

Intuition

Compute LCS length via memoized recursion, then recursively backtrack from (m, n) to build the supersequence.

Algorithm

  1. Compute memoized LCS matrix.
  2. Use memoized values to guide reconstruction.
  3. Return built string.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5
6using namespace std;
7
8class Solution {
9 int getLCS(int i, int j, const string& s1, const string& s2, vector<vector<int>>& memo) {
10 if (i == 0 || j == 0) return 0;
11 if (memo[i][j] != -1) return memo[i][j];
12
13 if (s1[i - 1] == s2[j - 1]) {
14 return memo[i][j] = 1 + getLCS(i - 1, j - 1, s1, s2, memo);
15 }
16 return memo[i][j] = max(getLCS(i - 1, j, s1, s2, memo), getLCS(i, j - 1, s1, s2, memo));
17 }
18public:
19 string shortestCommonSupersequence(string str1, string str2) {
20 int m = str1.length(), n = str2.length();
21 vector<vector<int>> memo(m + 1, vector<int>(n + 1, -1));
22 getLCS(m, n, str1, str2, memo);
23
24 // Fill remaining base cases
25 for (int i = 0; i <= m; ++i) memo[i][0] = 0;
26 for (int j = 0; j <= n; ++j) memo[0][j] = 0;
27
28 string res = "";
29 int i = m, j = n;
30 while (i > 0 && j > 0) {
31 if (str1[i - 1] == str2[j - 1]) {
32 res += str1[i - 1];
33 i--; j--;
34 } else if (memo[i - 1][j] > memo[i][j - 1]) {
35 res += str1[i - 1];
36 i--;
37 } else {
38 res += str2[j - 1];
39 j--;
40 }
41 }
42 while (i > 0) { res += str1[i - 1]; i--; }
43 while (j > 0) { res += str2[j - 1]; j--; }
44
45 reverse(res.begin(), res.end());
46 return res;
47 }
48};
49
50int main() {
51 Solution sol;
52 cout << "SCS: " << sol.shortestCommonSupersequence("abac", "cab") << endl;
53 return 0;
54}

Time & Space Complexity

  • Time complexity: O(m * n)
  • Space complexity: O(m * n)

3. LCS Tabulation + Two-Pointer Backtracking

Intuition

Compute full LCS matrix iteratively in O(m * n). Backtrack from (m, n) down to (0, 0), appending characters and reversing at the end.

Algorithm

  1. Build 2D table dp[m+1][n+1] with standard LCS recurrence.
  2. Initialize two pointers i = m, j = n, and empty string builder.
  3. While i > 0 && j > 0:
  4. If str1[i - 1] == str2[j - 1]: append char once, i--, j--.
  5. Else if dp[i - 1][j] > dp[i][j - 1]: append str1[i - 1], i--.
  6. Else: append str2[j - 1], j--.
  7. Append remaining characters from str1 or str2.
  8. Reverse the string builder and return.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5
6using namespace std;
7
8class Solution {
9public:
10 string shortestCommonSupersequence(string str1, string str2) {
11 int m = str1.size(), n = str2.size();
12 vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
13
14 for (int i = 1; i <= m; ++i) {
15 for (int j = 1; j <= n; ++j) {
16 if (str1[i - 1] == str2[j - 1]) {
17 dp[i][j] = 1 + dp[i - 1][j - 1];
18 } else {
19 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
20 }
21 }
22 }
23
24 string result = "";
25 int i = m, j = n;
26 while (i > 0 && j > 0) {
27 if (str1[i - 1] == str2[j - 1]) {
28 result += str1[i - 1];
29 i--; j--;
30 } else if (dp[i - 1][j] > dp[i][j - 1]) {
31 result += str1[i - 1];
32 i--;
33 } else {
34 result += str2[j - 1];
35 j--;
36 }
37 }
38
39 while (i > 0) { result += str1[i - 1]; i--; }
40 while (j > 0) { result += str2[j - 1]; j--; }
41
42 reverse(result.begin(), result.end());
43 return result;
44 }
45};
46
47int main() {
48 Solution sol;
49 cout << "SCS: " << sol.shortestCommonSupersequence("abac", "cab") << endl;
50 return 0;
51}

Time & Space Complexity

  • Time complexity: O(m * n)
  • Space complexity: O(m * n)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Recursive InterleavingO(2^(m + n))O(m + n)Exhaustive branching over string characters.String copying and recursive branches
2.Memoized LCS + BacktrackingO(m * n)O(m * n)Memoize LCS table and reconstruct path.Call stack
3.LCS Tabulation + Two-Pointer BacktrackingOptimalO(m * n)O(m * n)Iteratively fill LCS matrix and backtrack from (m, n).None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Forgetting to append the remaining characters of str1 or str2 when one pointer hits 0.

Pitfall 2:

Forgetting to reverse the string at the end of the backward traversal.

Pitfall 3:

Appending matching characters twice instead of once.

Crucial Edge Cases to Validate:

  • str1 == str2: Answer is just str1.
  • Completely disjoint strings (no common letters): Returns str1 + str2.
  • One string is a subsequence of the other: Returns the longer string.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the fundamental identity: len(SCS) = len(str1) + len(str2) - len(LCS). It impresses interviewers and establishes clarity before coding.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why can't we use a 1D rolling array if the problem requires returning the ACTUAL supersequence string (not just its length)?

Back to DSA Sheet