Close
Topic list
Shortest Common Supersequence
HARD
Strings
Dynamic Programming
Topics (Covered in this problem)
Problem solved
Skill meter
Strings
-
Dynamic Programming
-
Other topics
Problem solved
Skill meter
Matrices (2D Arrays)
-
Sorting
-
Binary Search
-
-
Stacks & Queues
-
Trees
-
Graph
-
Greedy
-
Tries
-
Arrays
-
Binary Search Trees
-
Heap
-
Bit Manipulation
-

# Shortest Common Supersequence

Contributed by
TanishkTonk
Hard
Share

## Problem Statement

#### 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, Constraints, Images )
##### 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
``````
Console