Shortest Common Supersequence - Practice Coding Problems

Shortest Common Supersequence - Problem

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

If there are multiple valid strings, return any of them.

A string s is a subsequence of string t if deleting some number of characters from t (possibly 0) results in the string s.

Input & Output

Example 1 — Basic Case

$ Input: str1 = "ab", str2 = "ac"

› Output: "aacb"

💡 Note: One possible supersequence is "aacb": 'a' appears in both strings, so we include it once, then 'a' from str2, then 'c' from str2, then 'b' from str1

Example 2 — No Common Characters

$ Input: str1 = "abc", str2 = "def"

› Output: "abcdef"

💡 Note: Since there are no common characters, we simply concatenate: "abc" + "def" = "abcdef"

Example 3 — Longer Common Subsequence

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

› Output: "cabac"

💡 Note: LCS is "ab", so we merge optimally: 'c' from str2, then common 'a', then common 'b', then remaining 'a', 'c' from str1

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Strings

Two strings that need to be merged: str1="ab", str2="ac"

Find Common Parts

Identify longest common subsequence to avoid duplication

Build Supersequence

Merge optimally to create shortest result: "aacb"

Key Takeaway

🎯 Key Insight: Use LCS to identify common parts and include them only once in the final supersequence

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Facebook 6

The key insight is to find the Longest Common Subsequence first, then build the supersequence by including common characters only once. The dynamic programming approach with LCS provides optimal O(m×n) solution. Time: O(m×n), Space: O(m×n)

Common Approaches

Approach	Time	Space	Notes
✓ Recursive with Memoization	O(m×n)	O(m×n)	Top-down recursive approach with caching to avoid redundant calculations
Dynamic Programming with LCS	O(m×n)	O(m×n)	Use Longest Common Subsequence to build optimal supersequence
Brute Force - Try All Interleavings	O(2^(m+n))	O(m+n)	Generate all possible ways to interleave characters from both strings

Recursive with Memoization — Algorithm Steps

Define recursive function with current positions in both strings
Use memoization to cache results for each state
For each call, try taking character from str1, str2, or both if they match

Visualization

Tap to expand

Step-by-Step Walkthrough

Recursive Calls

Explore all possible ways to build supersequence

Cache Results

Store computed results to avoid recomputation

Optimal Choice

Return shortest valid supersequence

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Simple memoization using a basic approach
char* solution(char* str1, char* str2) {
    int m = strlen(str1), n = strlen(str2);
    
    // Use similar DP approach as it's complex to implement full memoization in C
    int** dp = malloc((m + 1) * sizeof(int*));
    for (int i = 0; i <= m; i++) {
        dp[i] = calloc(n + 1, sizeof(int));
    }
    
    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] = dp[i-1][j] > dp[i][j-1] ? dp[i-1][j] : dp[i][j-1];
            }
        }
    }
    
    char* result = malloc((m + n + 1) * sizeof(char));
    int pos = 0;
    int i = m, j = n;
    
    while (i > 0 && j > 0) {
        if (str1[i-1] == str2[j-1]) {
            result[pos++] = str1[i-1];
            i--;
            j--;
        } else if (dp[i-1][j] > dp[i][j-1]) {
            result[pos++] = str1[i-1];
            i--;
        } else {
            result[pos++] = str2[j-1];
            j--;
        }
    }
    
    while (i > 0) result[pos++] = str1[i-1], i--;
    while (j > 0) result[pos++] = str2[j-1], j--;
    
    result[pos] = '\0';
    
    // Reverse
    for (int k = 0; k < pos / 2; k++) {
        char temp = result[k];
        result[k] = result[pos - 1 - k];
        result[pos - 1 - k] = temp;
    }
    
    for (int k = 0; k <= m; k++) {
        free(dp[k]);
    }
    free(dp);
    
    return result;
}

int main() {
    char str1[1001], str2[1001];
    fgets(str1, sizeof(str1), stdin);
    str1[strcspn(str1, "\n")] = 0;
    fgets(str2, sizeof(str2), stdin);
    str2[strcspn(str2, "\n")] = 0;
    
    char* result = solution(str1, str2);
    printf("%s\n", result);
    free(result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m×n)

Each unique state (i,j) is computed only once due to memoization

✓ Linear Growth

Space Complexity

O(m×n)

Memoization table stores results for all state combinations plus recursion stack

⚡ Linearithmic Space

89.0K Views

Medium Frequency

~25 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Recursive with Memoization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler