Is Find the Shortest Superstring easy or hard?

Find the Shortest Superstring is categorized as Hard. The challenge comes from recognizing that the problem reduces to a Traveling Salesman–style dynamic programming problem using bitmasks, combined with careful string overlap computation.

Find the Shortest Superstring Python/Java solution

Most implementations compute overlaps, run DP with bitmask states, and store parent pointers to reconstruct the order. Python, Java, and C++ solutions typically follow the same structure: overlap preprocessing, subset DP iteration, then building the final string using the optimal ordering.

How to solve Find the Shortest Superstring in O(n^2 · 2^n)?

First compute the overlap length between every pair of strings. Use a bitmask to represent which words are included and maintain dp[mask][i] for the best overlap when ending with word i. Transition by adding an unused word j and updating overlap using the precomputed matrix. After filling DP states, reconstruct the path that maximizes total overlap and build the final merged string.

What is the best approach for Find the Shortest Superstring?

Dynamic Programming with bitmasking is the most reliable approach. Precompute overlaps between every pair of words and run subset DP where dp[mask][i] tracks the best overlap ending with word i. The algorithm runs in O(n^2 · 2^n) time and reconstructs the optimal ordering that produces the shortest superstring.

Is Find the Shortest Superstring asked at Google/Amazon/Meta?

Shortest superstring style problems appear in interviews at companies like Google, Amazon, and Meta because they combine graph modeling with dynamic programming. The problem tests your ability to transform a string problem into a Traveling Salesman–style DP using bitmasks.

What data structure is used in Find the Shortest Superstring?

The solution uses arrays or matrices to store pairwise overlaps, plus a DP table indexed by bitmask and last node. Bitmasks efficiently represent subsets of words, enabling transitions similar to Hamiltonian path or TSP dynamic programming.

What is the time complexity of Find the Shortest Superstring?

The optimal DP + bitmask solution runs in O(n^2 · 2^n) time and O(n · 2^n) space, where n is the number of strings. Pairwise overlap preprocessing adds O(n^2 · m) where m is the average string length. Brute-force permutation solutions take O(n! · n · m) and are only feasible for very small inputs.

Description Solution Video 26:31

943. Find the Shortest Superstring

Hard45.8% acceptance2 companies

Given an array of strings words, return the smallest string that contains each string in words as a substring. If there are multiple valid strings of the smallest length, return any of them.

You may assume that no string in words is a substring of another string in words.

Example 1:

Input: words = ["alex","loves","leetcode"]
Output: "alexlovesleetcode"
Explanation: All permutations of "alex","loves","leetcode" would also be accepted.

Example 2:

Input: words = ["catg","ctaagt","gcta","ttca","atgcatc"]
Output: "gctaagttcatgcatc"

Constraints:

1 <= words.length <= 12
1 <= words[i].length <= 20
words[i] consists of lowercase English letters.
All the strings of words are unique.

Asked at 2 companies

D. E. Shaw

Google

Topics

26:31

Still stuck?Read 5 approaches, or watch a walkthrough.

Open solution

943. Find the Shortest Superstring

Asked at 2 companies

Topics

Similar problems