Shortest Common Supersequence

Last Updated : 8 Nov, 2025

Given two strings s1 and s2, Find the length of the shortest string that has both s1 and s2 as subsequences.
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.

Examples: 

Input: s1 = "geek", s2 = "eke"
Output: 5
Explanation: String "geeke" has both string "geek" and "eke" as subsequences.

Input: s1 = "AGGTAB", s2 = "GXTXAYB"
Output: 9
Explanation: String "AGXGTXAYB" has both string "AGGTAB" and "GXTXAYB" as subsequences.

Try it on GfG Practice
redirect icon

Table of Content

[Naive Approach] Using Recursion - O(2^(m+n)) Time and O(m+n) Auxiliary Space

Our goal is to build the shortest string that contains both s1 and s2 as subsequences. A naive thought might be to simply merge all characters of both strings - but that actually gives the longest, not the shortest, supersequence because common characters get counted twice.
The key insight is: If a character appears in both strings and in the same order, we can include it only once in our supersequence.
However, when characters differ, we have choices — and recursion is perfect for exploring such choice-based problems.

We start comparing the characters of both strings from the end. If the last characters match: That character will definitely appear once in the supersequence. We include it and move one step back in both strings.
If the last characters don’t match: We have two options:

  • Include the last character of s1 and keep s2 as it is.
  • Include the last character of s2 and keep s1 as it is.

We choose the option that gives the shorter result. When one string becomes empty, it means there’s nothing left to match. So, we simply add all remaining characters of the other string to complete the sequence.

C++ 
//Driver Code Starts
#include <iostream>
#include<vector>
using namespace std;
//Driver Code Ends


int minSuperSeqRec(string &s1, string &s2, int m, int n) {

    // If s1 is empty, take all of s2
    if (m == 0)
        return n;

    // If s2 is empty, take all of s1
    if (n == 0)
        return m;

    // If last chars match, include once
    if (s1[m - 1] == s2[n - 1])
        return 1 + minSuperSeqRec(s1, s2, m - 1, n - 1);

    // If not match, try both options and take min
    return 1 + min(minSuperSeqRec(s1, s2, m - 1, n),
                   minSuperSeqRec(s1, s2, m, n - 1));
}

int minSuperSeq(string &s1, string &s2) {
    return minSuperSeqRec(s1, s2, s1.size(), s2.size());
}


//Driver Code Starts
int main() {
    string s1 = "AGGTAB";
    string s2 = "GXTXAYB";

    int res = minSuperSeq(s1, s2);

    cout << res << endl;

    return 0;
}

//Driver Code Ends
Java 
//Driver Code Starts
import java.util.Arrays;

class GFG {
//Driver Code Ends

    static int minSuperSeqRec(String s1, String s2, int m, int n) {

        // If s1 is empty, take all of s2
        if (m == 0)
            return n;

        // If s2 is empty, take all of s1
        if (n == 0)
            return m;

        // If last chars match, include once
        if (s1.charAt(m - 1) == s2.charAt(n - 1))
            return 1 + minSuperSeqRec(s1, s2, m - 1, n - 1);

        // If not match, try both options and take min
        return 1 + Math.min(minSuperSeqRec(s1, s2, m - 1, n),
                            minSuperSeqRec(s1, s2, m, n - 1));
    }

    static int minSuperSeq(String s1, String s2) {
        return minSuperSeqRec(s1, s2, s1.length(), s2.length());
    }


//Driver Code Starts
    public static void main(String[] args) {
        String s1 = "AGGTAB";
        String s2 = "GXTXAYB";

        int res = minSuperSeq(s1, s2);

        System.out.println(res);
    }
}

//Driver Code Ends
Python 
def minSuperSeqRec(s1, s2, m, n):
    # If s1 is empty, take all of s2
    if m == 0:
        return n

    # If s2 is empty, take all of s1
    if n == 0:
        return m

    # If last chars match, include once
    if s1[m - 1] == s2[n - 1]:
        return 1 + minSuperSeqRec(s1, s2, m - 1, n - 1)

    # If not match, try both options and take min
    return 1 + min(minSuperSeqRec(s1, s2, m - 1, n),
                   minSuperSeqRec(s1, s2, m, n - 1))


def minSuperSeq(s1, s2):
    return minSuperSeqRec(s1, s2, len(s1), len(s2))



#Driver Code Starts
if __name__ == "__main__":
    s1 = "AGGTAB"
    s2 = "GXTXAYB"
    
    res = minSuperSeq(s1, s2)
    print(res)

#Driver Code Ends
C# 
//Driver Code Starts
using System;

class GFG {
//Driver Code Ends

    static int minSuperSeqRec(string s1, string s2, int m, int n) {

        // If s1 is empty, take all of s2
        if (m == 0)
            return n;

        // If s2 is empty, take all of s1
        if (n == 0)
            return m;

        // If last chars match, include once
        if (s1[m - 1] == s2[n - 1])
            return 1 + minSuperSeqRec(s1, s2, m - 1, n - 1);

        // If not match, try both options and take min
        return 1 + Math.Min(minSuperSeqRec(s1, s2, m - 1, n),
                            minSuperSeqRec(s1, s2, m, n - 1));
    }

    static int minSuperSeq(string s1, string s2) {
        return minSuperSeqRec(s1, s2, s1.Length, s2.Length);
    }


//Driver Code Starts
    static void Main() {
        string s1 = "AGGTAB";
        string s2 = "GXTXAYB";

        int res = minSuperSeq(s1, s2);
        Console.WriteLine(res);
    }
}

//Driver Code Ends
JavaScript 
function minSuperSeqRec(s1, s2, m, n) {
    // If s1 is empty, take all of s2
    if (m === 0)
        return n;

    // If s2 is empty, take all of s1
    if (n === 0)
        return m;

    // If last chars match, include once
    if (s1[m - 1] === s2[n - 1])
        return 1 + minSuperSeqRec(s1, s2, m - 1, n - 1);

    // If not match, try both options and take min
    return 1 + Math.min(minSuperSeqRec(s1, s2, m - 1, n),
                        minSuperSeqRec(s1, s2, m, n - 1));
}

function minSuperSeq(s1, s2) {
    return minSuperSeqRec(s1, s2, s1.length, s2.length);
}


//Driver Code
//Driver Code Starts
let s1 = "AGGTAB";
let s2 = "GXTXAYB";

let res = minSuperSeq(s1, s2);
console.log(res);

//Driver Code Ends

Output
9

[Better Approach - 1] Using Top-Down DP (Memoization) - O(m*n) Time and O(m*n) Space

If we look closely at the previous recursive approach, we can notice the same subproblems are solved multiple times. This makes a program inefficient.
To handle this, we use Dynamic Programming with Memoization.

The idea is simple: In the recursive approach, our result depends on two parameters - the current indices m and n. So, we create a 2D array dp of size (m+1) × (n+1), where dp[i][j] stores the length of the shortest common supersequence for the first i characters of s1 and the first j characters of s2.
Before solving any subproblem (i, j), we first check:
If it has been solved before, we simply return the stored value. Otherwise, we compute it recursively, store the result in dp[i][j], and reuse it later whenever needed.

C++ 
//Driver Code Starts
#include <iostream>
#include<vector>
using namespace std;
//Driver Code Ends


int minSuperSeqRec(string &s1, string &s2, int m, int n,
                   vector<vector<int>> &dp) {
  
    // If s1 is empty, take all of s2
    if (m == 0)
        return n;

     // If s2 is empty, take all of s1
    if (n == 0)
        return m;

   // check before solve the subproblem
    if (dp[m][n] != -1)
        return dp[m][n];

   // If last chars match, include once
    if (s1[m - 1] == s2[n - 1])
        return dp[m][n] = 1 + minSuperSeqRec(s1, s2, m - 1, n - 1, dp);

    // If not match, try both options and take min 
    // and store it in dp array
    return dp[m][n] =
               1 + min(minSuperSeqRec(s1, s2, m - 1, n, dp), 
                       minSuperSeqRec(s1, s2, m, n - 1, dp));
}

int minSuperSeq(string &s1, string &s2) {
  
    int m = s1.size();
    int n = s2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, -1));
    return minSuperSeqRec(s1, s2, m, n, dp);
}


//Driver Code Starts
int main() {
  
    string s1 = "AGGTAB";
    string s2 = "GXTXAYB";

    int res = minSuperSeq(s1, s2);

    cout << res << endl;

    return 0;
}
//Driver Code Ends
Java 
//Driver Code Starts
import java.util.Arrays;

public class GFG {
//Driver Code Ends


    static int minSuperSeqRec(String s1, String s2, int m, int n,
                              int[][] dp) {
  
        // If s1 is empty, take all of s2
        if (m == 0)
            return n;

        // If s2 is empty, take all of s1
        if (n == 0)
            return m;

        // check before solve the subproblem
        if (dp[m][n] != -1)
            return dp[m][n];

        // If last chars match, include once
        if (s1.charAt(m - 1) == s2.charAt(n - 1))
            return dp[m][n] = 1 + minSuperSeqRec(s1, s2, m - 1, n - 1, dp);

        // If not match, try both options and take min 
        // and store it in dp array
        return dp[m][n] =
                   1 + Math.min(minSuperSeqRec(s1, s2, m - 1, n, dp),
                                minSuperSeqRec(s1, s2, m, n - 1, dp));
    }

    static int minSuperSeq(String s1, String s2) {
  
        int m = s1.length();
        int n = s2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int[] row : dp) Arrays.fill(row, -1);
        return minSuperSeqRec(s1, s2, m, n, dp);
    }


//Driver Code Starts
    public static void main(String[] args) {
  
        String s1 = "AGGTAB";
        String s2 = "GXTXAYB";

        int res = minSuperSeq(s1, s2);

        System.out.println(res);
    }
}

//Driver Code Ends
Python 
def minSuperSeqRec(s1, s2, m, n, dp):
  
    # If s1 is empty, take all of s2
    if m == 0:
        return n

    # If s2 is empty, take all of s1
    if n == 0:
        return m

    # check before solve the subproblem
    if dp[m][n] != -1:
        return dp[m][n]

    # If last chars match, include once
    if s1[m - 1] == s2[n - 1]:
        dp[m][n] = 1 + minSuperSeqRec(s1, s2, m - 1, n - 1, dp)
        return dp[m][n]

    # If not match, try both options and take min 
    # and store it in dp array
    dp[m][n] = 1 + min(minSuperSeqRec(s1, s2, m - 1, n, dp),
                       minSuperSeqRec(s1, s2, m, n - 1, dp))
    return dp[m][n]


def minSuperSeq(s1, s2):
  
    m = len(s1)
    n = len(s2)
    dp = [[-1] * (n + 1) for _ in range(m + 1)]
    return minSuperSeqRec(s1, s2, m, n, dp)



#Driver Code Starts
if __name__ == "__main__":
    s1 = "AGGTAB"
    s2 = "GXTXAYB"
    res = minSuperSeq(s1, s2)
    print(res)

#Driver Code Ends
C# 
//Driver Code Starts
using System;

class GFG {
//Driver Code Ends


    static int minSuperSeqRec(string s1, string s2, int m, int n, int[,] dp) {
  
        // If s1 is empty, take all of s2
        if (m == 0)
            return n;

        // If s2 is empty, take all of s1
        if (n == 0)
            return m;

        // check before solve the subproblem
        if (dp[m, n] != -1)
            return dp[m, n];

        // If last chars match, include once
        if (s1[m - 1] == s2[n - 1])
            return dp[m, n] = 1 + minSuperSeqRec(s1, s2, m - 1, n - 1, dp);

        // If not match, try both options and take min 
        // and store it in dp array
        return dp[m, n] =
               1 + Math.Min(minSuperSeqRec(s1, s2, m - 1, n, dp),
                            minSuperSeqRec(s1, s2, m, n - 1, dp));
    }

    static int minSuperSeq(string s1, string s2) {
  
        int m = s1.Length;
        int n = s2.Length;
        int[,] dp = new int[m + 1, n + 1];

        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++)
                dp[i, j] = -1;
        }

        return minSuperSeqRec(s1, s2, m, n, dp);
    }


//Driver Code Starts
    static void Main() {
  
        string s1 = "AGGTAB";
        string s2 = "GXTXAYB";

        int res = minSuperSeq(s1, s2);

        Console.WriteLine(res);
    }
}

//Driver Code Ends
JavaScript 
function minSuperSeqRec(s1, s2, m, n, dp) {
  
    // If s1 is empty, take all of s2
    if (m === 0)
        return n;

    // If s2 is empty, take all of s1
    if (n === 0)
        return m;

    // check before solve the subproblem
    if (dp[m][n] !== -1)
        return dp[m][n];

    // If last chars match, include once
    if (s1[m - 1] === s2[n - 1])
        return dp[m][n] = 1 + minSuperSeqRec(s1, s2, m - 1, n - 1, dp);

    // If not match, try both options and take min 
    // and store it in dp array
    return dp[m][n] =
               1 + Math.min(minSuperSeqRec(s1, s2, m - 1, n, dp),
                            minSuperSeqRec(s1, s2, m, n - 1, dp));
}

function minSuperSeq(s1, s2) {
  
    const m = s1.length;
    const n = s2.length;
    const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(-1));
    return minSuperSeqRec(s1, s2, m, n, dp);
}


//Driver Code
//Driver Code Starts
const s1 = "AGGTAB";
const s2 = "GXTXAYB";

const res = minSuperSeq(s1, s2);
console.log(res);

//Driver Code Ends

Output
9

[Better Approach - 2] Using Bottom-Up DP (Tabulation) - O(m*n) Time and O(m*n) Space

In the recursive and memoized methods, we broke the problem into smaller subproblems using function calls - which also involved extra stack space. In this approach, we will iteratively compute and store results for all smaller subproblems in a 2D DP table and then use these results to build up the final answer.

We create a 2D DP array dp of size (m + 1) x (n + 1), where m and n are the lengths of s1 and s2. First, we define some base cases to start the iteration: dp[i][0] = i and dp[0][j] = j.
This means if one string is empty, the shortest supersequence is simply the other string. Next, we iterate over both strings character by character:

  • If the characters match, we include this character only once: dp[i][j] = 1 + dp[i-1][j-1]
  • If the characters don’t match, we have two choices - take a character from s1 or from s2 - and we choose the one that gives the smaller length: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1])

After filling the entire table, dp[m][n] will hold the length of the Shortest Common Supersequence (SCS) of s1 and s2.

C++ 
//Driver Code Starts
#include <iostream>
#include<vector>
using namespace std;
//Driver Code Ends


int minSuperSeq(string &s1, string &s2) {
    int m = s1.size();
    int n = s2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));

    // If s2 is empty, take all of s1
    for (int i = 0; i <= m; i++)
        dp[i][0] = i;

    // If s1 is empty, take all of s2
    for (int j = 0; j <= n; j++)
        dp[0][j] = j;

    // Fill the dp table iteratively
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {

            // If last chars match, include once
            if (s1[i - 1] == s2[j - 1])
                dp[i][j] = 1 + dp[i - 1][j - 1];

            // If not match, take min of both options
            else
                dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1]);
        }
    }

    return dp[m][n];
}


//Driver Code Starts
int main() {
  
    string s1 = "AGGTAB";
    string s2 = "GXTXAYB";

    int res = minSuperSeq(s1, s2);

    cout << res << endl;

    return 0;
}

//Driver Code Ends
Java 
//Driver Code Starts
import java.util.Arrays;

public class GFG {
//Driver Code Ends


    static int minSuperSeq(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();
        int[][] dp = new int[m + 1][n + 1];

        // If s2 is empty, take all of s1
        for (int i = 0; i <= m; i++)
            dp[i][0] = i;

        // If s1 is empty, take all of s2
        for (int j = 0; j <= n; j++)
            dp[0][j] = j;

        // Fill the dp table iteratively
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {

                // If last chars match, include once
                if (s1.charAt(i - 1) == s2.charAt(j - 1))
                    dp[i][j] = 1 + dp[i - 1][j - 1];

                // If not match, take min of both options
                else
                    dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1]);
            }
        }

        return dp[m][n];
    }


//Driver Code Starts
    public static void main(String[] args) {
        String s1 = "AGGTAB";
        String s2 = "GXTXAYB";

        int res = minSuperSeq(s1, s2);

        System.out.println(res);
    }
}

//Driver Code Ends
Python 
def minSuperSeq(s1, s2):
    m = len(s1)
    n = len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # If s2 is empty, take all of s1
    for i in range(m + 1):
        dp[i][0] = i

    # If s1 is empty, take all of s2
    for j in range(n + 1):
        dp[0][j] = j

    # Fill the dp table iteratively
    for i in range(1, m + 1):
        for j in range(1, n + 1):

            # If last chars match, include once
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = 1 + dp[i - 1][j - 1]

            # If not match, take min of both options
            else:
                dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1])

    return dp[m][n]



#Driver Code Starts
if __name__ == "__main__":
    s1 = "AGGTAB"
    s2 = "GXTXAYB"
    
    res = minSuperSeq(s1, s2)
    print(res)

#Driver Code Ends
C# 
//Driver Code Starts
using System;

class GFG {
//Driver Code Ends


    static int minSuperSeq(string s1, string s2) {
        int m = s1.Length;
        int n = s2.Length;
        int[,] dp = new int[m + 1, n + 1];

        // If s2 is empty, take all of s1
        for (int i = 0; i <= m; i++)
            dp[i, 0] = i;

        // If s1 is empty, take all of s2
        for (int j = 0; j <= n; j++)
            dp[0, j] = j;

        // Fill the dp table iteratively
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {

                // If last chars match, include once
                if (s1[i - 1] == s2[j - 1])
                    dp[i, j] = 1 + dp[i - 1, j - 1];

                // If not match, take min of both options
                else
                    dp[i, j] = 1 + Math.Min(dp[i - 1, j], dp[i, j - 1]);
            }
        }

        return dp[m, n];
    }


//Driver Code Starts
    static void Main() {
        string s1 = "AGGTAB";
        string s2 = "GXTXAYB";

        int res = minSuperSeq(s1, s2);

        Console.WriteLine(res);
    }
}

//Driver Code Ends
JavaScript 
function minSuperSeq(s1, s2) {
    const m = s1.length;
    const n = s2.length;
    const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));

    // If s2 is empty, take all of s1
    for (let i = 0; i <= m; i++)
        dp[i][0] = i;

    // If s1 is empty, take all of s2
    for (let j = 0; j <= n; j++)
        dp[0][j] = j;

    // Fill the dp table iteratively
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {

            // If last chars match, include once
            if (s1[i - 1] === s2[j - 1])
                dp[i][j] = 1 + dp[i - 1][j - 1];

            // If not match, take min of both options
            else
                dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1]);
        }
    }

    return dp[m][n];
}


//Driver Code
//Driver Code Starts
const s1 = "AGGTAB";
const s2 = "GXTXAYB";

const res = minSuperSeq(s1, s2);
console.log(res);

//Driver Code Ends

Output
9

[Expected Approach - 1] Using Space Optimized DP - O(m*n) Time and O(n) Space

In the previous dynamic programming approach, we derived the relation between states as:
if (s1[i-1] == s2[j-1]) dp[i][j] = 1 + dp[i-1][j-1] that means both characters are the same, so we take it once.
else dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1]) we take the minimum of both possibilities.
If we observe carefully, to calculate the current cell dp[i][j], we only need values from: the previous row - dp[i-1][j-1] and dp[i-1][j], and the current row -> dp[i][j-1].
This means we don’t need to store the entire 2D table of size (m + 1) x (n + 1).

We can optimize the space by using only two 1D arrays - one for the current row and one for the previous row. So instead of maintaining a complete DP matrix, we keep a prev array to store the previous row. Create a curr array for the current row calculations. After finishing one iteration of i, assign prev = curr for the next iteration.

C++ 
//Driver Code Starts
#include <iostream>
#include <vector>
using namespace std;
//Driver Code Ends


int minSuperSeq(string &s1, string &s2) {
    int m = s1.size();
    int n = s2.size();

    // Use two 1D arrays to store previous and current row
    vector<int> prev(n + 1, 0), curr(n + 1, 0);

    // If s1 is empty, take all of s2
    for (int j = 0; j <= n; j++)
        prev[j] = j;

    // Iterate through both strings
    for (int i = 1; i <= m; i++) {

        // If s2 is empty, take all of s1
        curr[0] = i;

        for (int j = 1; j <= n; j++) {

            // If last chars match, include once
            if (s1[i - 1] == s2[j - 1])
                curr[j] = 1 + prev[j - 1];

            // If not match, take min of both options
            else
                curr[j] = 1 + min(prev[j], curr[j - 1]);
        }

        // Move current row to previous for next iteration
        prev = curr;
    }

    return prev[n];
}


//Driver Code Starts
int main() {

    string s1 = "AGGTAB";
    string s2 = "GXTXAYB";

    int res = minSuperSeq(s1, s2);

    cout << res << endl;

    return 0;
}

//Driver Code Ends
Java 
//Driver Code Starts
import java.util.Arrays;

public class GFG {
//Driver Code Ends


    static int minSuperSeq(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();

        // Use two 1D arrays to store previous and current row
        int[] prev = new int[n + 1];
        int[] curr = new int[n + 1];

        // If s1 is empty, take all of s2
        for (int j = 0; j <= n; j++)
            prev[j] = j;

        // Iterate through both strings
        for (int i = 1; i <= m; i++) {

            // If s2 is empty, take all of s1
            curr[0] = i;

            for (int j = 1; j <= n; j++) {

                // If last chars match, include once
                if (s1.charAt(i - 1) == s2.charAt(j - 1))
                    curr[j] = 1 + prev[j - 1];

                // If not match, take min of both options
                else
                    curr[j] = 1 + Math.min(prev[j], curr[j - 1]);
            }

            // Move current row to previous for next iteration
            prev = curr.clone();
        }

        return prev[n];
    }


//Driver Code Starts
    public static void main(String[] args) {

        String s1 = "AGGTAB";
        String s2 = "GXTXAYB";

        int res = minSuperSeq(s1, s2);

        System.out.println(res);
    }
}

//Driver Code Ends
Python 
def minSuperSeq(s1, s2):
    m = len(s1)
    n = len(s2)

    # Use two 1D arrays to store previous and current row
    prev = [0] * (n + 1)
    curr = [0] * (n + 1)

    # If s1 is empty, take all of s2
    for j in range(n + 1):
        prev[j] = j

    # Iterate through both strings
    for i in range(1, m + 1):

        # If s2 is empty, take all of s1
        curr[0] = i

        for j in range(1, n + 1):

            # If last chars match, include once
            if s1[i - 1] == s2[j - 1]:
                curr[j] = 1 + prev[j - 1]

            # If not match, take min of both options
            else:
                curr[j] = 1 + min(prev[j], curr[j - 1])

        # Move current row to previous for next iteration
        prev = curr[:]

    return prev[n]



#Driver Code Starts
if __name__ == "__main__":
    s1 = "AGGTAB"
    s2 = "GXTXAYB"
    
    res = minSuperSeq(s1, s2)

print(res)

#Driver Code Ends
C# 
//Driver Code Starts
using System;

class GFG {
//Driver Code Ends


    static int minSuperSeq(string s1, string s2) {
        int m = s1.Length;
        int n = s2.Length;

        // Use two 1D arrays to store previous and current row
        int[] prev = new int[n + 1];
        int[] curr = new int[n + 1];

        // If s1 is empty, take all of s2
        for (int j = 0; j <= n; j++)
            prev[j] = j;

        // Iterate through both strings
        for (int i = 1; i <= m; i++) {

            // If s2 is empty, take all of s1
            curr[0] = i;

            for (int j = 1; j <= n; j++) {

                // If last chars match, include once
                if (s1[i - 1] == s2[j - 1])
                    curr[j] = 1 + prev[j - 1];

                // If not match, take min of both options
                else
                    curr[j] = 1 + Math.Min(prev[j], curr[j - 1]);
            }

            // Move current row to previous for next iteration
            Array.Copy(curr, prev, n + 1);
        }

        return prev[n];
    }


//Driver Code Starts
    static void Main() {

        string s1 = "AGGTAB";
        string s2 = "GXTXAYB";

        int res = minSuperSeq(s1, s2);

        Console.WriteLine(res);
    }
}

//Driver Code Ends
JavaScript 
function minSuperSeq(s1, s2) {
    const m = s1.length;
    const n = s2.length;

    // Use two 1D arrays to store previous and current row
    let prev = Array(n + 1).fill(0);
    let curr = Array(n + 1).fill(0);

    // If s1 is empty, take all of s2
    for (let j = 0; j <= n; j++)
        prev[j] = j;

    // Iterate through both strings
    for (let i = 1; i <= m; i++) {

        // If s2 is empty, take all of s1
        curr[0] = i;

        for (let j = 1; j <= n; j++) {

            // If last chars match, include once
            if (s1[i - 1] === s2[j - 1])
                curr[j] = 1 + prev[j - 1];

            // If not match, take min of both options
            else
                curr[j] = 1 + Math.min(prev[j], curr[j - 1]);
        }

        // Move current row to previous for next iteration
        prev = [...curr];
    }

    return prev[n];
}


//Driver Code
//Driver Code Starts
const s1 = "AGGTAB";
const s2 = "GXTXAYB";

const res = minSuperSeq(s1, s2);

console.log(res);

//Driver Code Ends

Output
9

[Expected Approach - 2] Using LCS Solution - O(m*n) Time and O(n) Space

If we look carefully, we are asked to find the Shortest Common Supersequence (SCS). Now, if both strings had no common characters, then we would need to take all characters from both strings. So, the length of SCS = len(s1) + len(s2). But when the strings share common characters, those common parts should appear only once in the final supersequence to minimize length. That’s where LCS (Longest Common Subsequence) helps us.

We know the relation between SCS and LCS: Length(SCS) = len(s1) + len(s2) − len(LCS)
So instead of directly computing SCS, we just need to find LCS length.
In LCS DP, to compute dp[i][j], we only need:

  • dp[i-1][j-1] - from previous row
  • dp[i][j-1] - from current row
  • dp[i-1][j] - from previous row

Hence, we can use only two 1D arrays - prev and curr.

C++ 
//Driver Code Starts
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//Driver Code Ends


int minSuperSeq(string &s1, string &s2) {
    int m = s1.size();
    int n = s2.size();

    vector<int> prev(n + 1, 0), curr(n + 1, 0);

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            
            // If chars match
            if (s1[i - 1] == s2[j - 1])
                curr[j] = 1 + prev[j - 1];
                
            // Else, take max from top or left
            else
                curr[j] = max(prev[j], curr[j - 1]);
        }
        // Move current row to previous
        prev = curr;
    }

    int lcsLen = prev[n];

    // SCS length = total - common part (LCS)
    return m + n - lcsLen;
}


//Driver Code Starts
int main() {
    string s1 = "AGGTAB";
    string s2 = "GXTXAYB";

    int res = minSuperSeq(s1, s2);

    cout << res << endl;
    return 0;
}

//Driver Code Ends
Java 
//Driver Code Starts
import java.util.Arrays;

public class GFG {
//Driver Code Ends

    static int minSuperSeq(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();

        int[] prev = new int[n + 1];
        int[] curr = new int[n + 1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {

                // If chars match
                if (s1.charAt(i - 1) == s2.charAt(j - 1))
                    curr[j] = 1 + prev[j - 1];

                // Else, take max from top or left
                else
                    curr[j] = Math.max(prev[j], curr[j - 1]);
            }
            // Move current row to previous
            prev = curr.clone();
        }

        int lcsLen = prev[n];

        // SCS length = total - common part (LCS)
        return m + n - lcsLen;
    }


//Driver Code Starts
    public static void main(String[] args) {
        String s1 = "AGGTAB";
        String s2 = "GXTXAYB";

        int res = minSuperSeq(s1, s2);
        System.out.println(res);
    }
}

//Driver Code Ends
Python 
def minSuperSeq(s1, s2):
    m, n = len(s1), len(s2)

    prev = [0] * (n + 1)
    curr = [0] * (n + 1)

    for i in range(1, m + 1):
        for j in range(1, n + 1):

            # If chars match
            if s1[i - 1] == s2[j - 1]:
                curr[j] = 1 + prev[j - 1]

            # Else, take max from top or left
            else:
                curr[j] = max(prev[j], curr[j - 1])

        # Move current row to previous
        prev = curr[:]

    lcsLen = prev[n]

    # SCS length = total - common part (LCS)
    return m + n - lcsLen


if __name__ == "__main__":
#Driver Code Starts
    s1 = "AGGTAB"
    s2 = "GXTXAYB"
    res = minSuperSeq(s1, s2)
print(res)

#Driver Code Ends
C# 
//Driver Code Starts
using System;

class GFG {
//Driver Code Ends

    static int minSuperSeq(string s1, string s2) {
        int m = s1.Length;
        int n = s2.Length;

        int[] prev = new int[n + 1];
        int[] curr = new int[n + 1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {

                // If chars match
                if (s1[i - 1] == s2[j - 1])
                    curr[j] = 1 + prev[j - 1];

                // Else, take max from top or left
                else
                    curr[j] = Math.Max(prev[j], curr[j - 1]);
            }
            // Move current row to previous
            Array.Copy(curr, prev, n + 1);
        }

        int lcsLen = prev[n];

        // SCS length = total - common part (LCS)
        return m + n - lcsLen;
    }


//Driver Code Starts
    static void Main() {
        string s1 = "AGGTAB";
        string s2 = "GXTXAYB";

        int res = minSuperSeq(s1, s2);
        Console.WriteLine(res);
    }
}

//Driver Code Ends
JavaScript 
function minSuperSeq(s1, s2) {
    const m = s1.length;
    const n = s2.length;

    let prev = new Array(n + 1).fill(0);
    let curr = new Array(n + 1).fill(0);

    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {

            // If chars match
            if (s1[i - 1] === s2[j - 1])
                curr[j] = 1 + prev[j - 1];

            // Else, take max from top or left
            else
                curr[j] = Math.max(prev[j], curr[j - 1]);
        }
        // Move current row to previous
        prev = [...curr];
    }

    const lcsLen = prev[n];

    // SCS length = total - common part (LCS)
    return m + n - lcsLen;
}


//Driver Code
//Driver Code Starts
const s1 = "AGGTAB";
const s2 = "GXTXAYB";
const res = minSuperSeq(s1, s2);
console.log(res);

//Driver Code Ends

Output
9


Comment
Article Tags:
Dynamic Programming
DSA
subsequence
LCS

Explore