Shortest Common Supersequence

Hard
0/120
Average time to solve is 25m
profile
Contributed by
164 upvotes
Asked in companies
HCL TechnologiesDream11Thought Works

Problem statement

Given two strings, ‘A’ and ‘B’. Return the shortest supersequence string ‘S’, containing both ‘A’ and ‘B’ as its subsequences. If there are multiple answers, return any of them.

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

For example: 
Suppose ‘A’ = “brute”, and ‘B’ = “groot”

The shortest supersequence will be “bgruoote”. As shown below, it contains both ‘A’ and ‘B’ as subsequences.

A   A A     A A
b g r u o o t e
  B B   B B B  

It can be proved that the length of supersequence for this input cannot be less than 8. So the output will be bgruoote.
Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of the input contains a single integer ‘T’ representing the no. of test cases.

The first line of each test case contains a single string ‘A’, denoting the first string described in the problem.

The second line of each test case contains a single string, ‘B’, denoting the second string described in the problem.

Output Format:

For each test case, print the shortest string ‘S’, which contains ‘A’ and ‘B’ as its subsequences.

Print a separate line for each test case.
Note: 
You are not required to print anything; it has already been taken care of. Just implement the function and return the answer.

Constraints:

1 ≤ T ≤ 100
1 ≤ |A|, |B| ≤ 1000
Both strings consist of only lowercase English letters.
1 ≤ Σ(|A|+|B|) ≤ 3000

Time limit: 1 Sec
Sample Input 1 :
2
brute
groot
bleed
blue
Sample Output 1 :
bgruoote
bleued
Explanation For Sample Input 1 :
For First Case - Same as explained in above example.

For the second case - 

‘A’ = “bleed”, and ‘B’ = “blue”

The shortest supersequence will be “bleued”. As shown below, it contains both ‘A’ and ‘B’ as subsequences.

A A A   A A
b l e u e d
B B   B B

It can be proved that the length of supersequence for this input cannot be less than 6. So the output will be bleued.
Sample Input 2 :
2
coding
ninjas
blinding
lights
Sample Output 2 :
codningjas
blindinghts
Hint

Can we do something recursively?

Approaches (3)
Brute Force (Recursive)

Let’s consider two substrings of length m and n, respectively. Now we can have two situations:-

 

Both the strings end with the same element:

So for finding their shortest common supersequence, what we have to do is we will shorten each string by removing the last element. Then we will find the shortest common supersequence of shortened lines, and then the removed element will be appended to the shortest common supersequence.

SCS(A[1…..m], B[1…...n]) = SCS(A[1….m-1], B[1...n-1]) + A[m]

 

Suppose two given strings are not ending at the same character:

In this situation the shortest common supersequence will be the shorter of the two sequences SCS(A[1...m-1], B[1..n]) + A[m] and SCS(A[1...m], B[1...n-1]) + B[n].


 

Algorithm:

 

Function shortestSupersequenceRec

Function arguments - string ‘A’, string ‘B’, integer ‘N’ representing the length of A’s prefix to be considered, integer ‘M’ representing the length of B’s prefix to be considered.
Returns - Shortest supersequence of A[1,2,...N] and B[1,2,...M].

  • If n == 0
    • Return prefix of B of length m
  • If m == 0
    • Return prefix of A of length n
  • If a[n-1] == b[n-1]
    • Return shortestSupersequenceRec(a, b, n-1, m-1) + a[n-1]
  • Declare and initialize string sa = shortestSupersequenceRec(a, b, n-1, m) + a[n-1]
  • Declare and initialize string sb = shortestSupersequenceRec(a, b, n, m-1) + b[m-1]
  • Return the shorter string out of sa and sb

 

Given Function

  • Declare and initialize integers n = length of A and m = length of B
  • Return shortestSupersequenceRec(a, b, n, m)
Time Complexity

O((N + M) * 2^(N + M)) where N and M are lengths of the given strings.

 

At each step, we are doing at max two recursive calls. No. of levels in the recursion can be at most O(N + M). So the total number of calls will be 2 ^ (N + M). At each call, we are doing O(N) operations to return a string. So total time will be equal to O((N + M) * 2^(N + M)).

Space Complexity

O((N + M) ^ 2) where N and M are lengths of the given strings.

 

Recursion stack can be at most max(N, M) deep, i.e., O(N + M). We require space to store strings of length O(N + M) at each step. So total space required will be O(N + M) * O(N + M) = O((N + M) ^ 2).

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Shortest Common Supersequence
Full screen
Console