Shortest Superstring Cover Problem

Shortest Superstring Cover Problem — ExecCode Hard DSA Practice

Solve the Shortest Superstring Cover problem on ExecCode. Free online hard DSA practice in DP. Write and run code in Java, C++, Python — no signup required to run.

Problem description

Find the shortest string that contains every given word as a contiguous substring. Words may overlap. This is TSP on overlap weights — a notorious OA/research crossover problem. If several superstrings have the same length, return the lexicographically smallest. Return one shortest superstring. You are given: words — unique non-empty lowercase fragments, n <= 8 Return a string covering every word. Concatenating without overlap is always valid but rarely shortest.

Examples

Input {'words': ['catg', 'ctaagt', 'gcta', 'ttca', 'atgcatc']}; Output gctaagttcatgcatc. Input {'words': ['ab', 'bc']}; Output abc. Input {'words': ['aa']}; Output aa

Constraints

Overlaps may be partial prefixes/suffixes

Practice Shortest Superstring Cover free on ExecCode. Browse DSA problems, topic map, and placement guides.