How to find the shortest common superstring [closed]

Question

Closed. This question needs details or clarity. It is not currently accepting answers.

---

Want to improve this question? As written, this question is lacking some of the information it needs to be answered. If the author adds details in comments, consider editing them into the question. Once there's sufficient detail to answer, vote to reopen the question.

Closed 2 years ago.

Improve this question

Problem statement: You are given an array of strings. Each element (string) of array is of size 2. You are supposed to find the length of shortest possible string such that every element of the array is a subsequence in that string. And we also have to return the number of such strings possible of that length. Example : ["ab","cd"]

"abcd", so 4 is the shortest length possible. possible combinations : abcd and acbd so answer is : 4 2 where 2 is the number of such strings possible of that length. (note : abacd is possible too but it's not shortest(length is 5). )

More examples:
example 1:
["aa","ac"]
Answer : 3 2
"aac" and "aca"

example 2:
["aa","ab","ac","ba","bb","bc","ca","cb","cc"]
answer : 6 36
length is 6 here, and total possible combinations is 36.

I tried to find a solution using graphs making each character a node but got stuck at one point. I also tried greedy but got nothing.
My findings are that we can find the length just by finding number of unique characters and if there is any string which is a reverse of any other string already present, then add +1 to the count of minimum length. So first part could be found out but i'm struggling at the second part of finding combinations. Could someone help me out here?

• candied_orange: Am I reading this right? Sure "aa" and "ac" are substrings of "aac". But how is "aa" a substring of "aca"? Are these strings considered to be toroidal?
• Deduplicator: Cannot [ab, cd] result in any of [abcd, acbd, acdb, cabd, cadb, cdab] thus 6 answers of length 4?
• candied_orange: @Deuplicator well sure, if these are sets not strings/sequences.

Answer 1

This is known as the shortest common supersequence problem, and it is known to be NP-hard. This means that there is no solution that doesn't take exponential time, and you might as well bite the bullet and try out every possible candidate in order rather than look for an efficient algorithm.