Assembling Fragments

Hard

A lab read a long chain piece by piece and ended up with a set of fragments. Build the shortest string that contains every fragment as a substring (a contiguous piece). No fragment is a substring of another, and all fragments are distinct. The shortest such string is guaranteed to be unique. Return it.

Example 1

fragments=["gatt", "ttaca", "acag"] → 'gattacag'

"gatt" and "ttaca" overlap on "tt", giving "gattaca"; then "acag" overlaps it on "aca", for "gattacag", 8 letters.

Example 2

fragments=["cde", "abc"] → 'abcde'

"abc" then "cde" share the "c" and give "abcde". The other order has no overlap and would take 6 letters.

Example 3

fragments=["hello"] → 'hello'

Constraints

1 ≤ len(fragments) ≤ 12
1 ≤ len(fragments[i]) ≤ 20
Fragments consist of lowercase English letters
All fragments are distinct and none is a substring of another
The shortest string is unique

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Bit Manipulation Array String Dynamic Programming Bitmask

Similar problems

Best Word Set From Tiles Hard Settle Up in the Fewest Transfers Hard Two Groups With the Same Average Hard Square-Sum Chains Hard Smallest Team With Every Skill Hard

Input

fragments=["gatt", "ttaca", "acag"]

Expected

'gattacag'

Run checks the first 3 tests in your browser. Submit checks all 34 tests on the server, hidden ones included.