Shortest Superstring Problem - GeeksforGeeks

Related: LeetCode 943 - Find the Shortest Superstring
Shortest Superstring Problem - GeeksforGeeks
Given a set of n strings arr[], find the smallest string that contains each string in the given set as substring. We may assume that no string in arr[] is substring of another string.
Examples:

Input:  arr[] = {"geeks", "quiz", "for"}  

Output: geeksquizfor    

Input:  arr[] = {"catg", "ctaagt", "gcta", "ttca", "atgcta"}  

Output: gctaagttcatgcatc

Shortest Superstring Greedy Approximate Algorithm
Shortest Superstring Problem is a NP Hard problem. A solution that always finds shortest superstring takes exponential time. Below is an Approximate Greedy algorithm.

Let arr[] be given set of strings.

1) Create an auxiliary array of strings, temp[].  Copy contents
   of arr[] to temp[]

2) While temp[] contains more than one strings
     a) Find the most overlapping string pair in temp[]. Let this
        pair be 'a' and 'b'. 
     b) Replace 'a' and 'b' with the string obtained in above step a

3) The only string left in temp[] is the result, return it.

Two strings are overlapping if prefix of one string is same suffix of other string or vice verse. The maximum overlap mean length of the matching prefix and suffix is maximum.

Read full article from Shortest Superstring Problem - GeeksforGeeks