Find the Shortest Superstring - Solution & Explanation
Problem Statement
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 <= 121 <= words[i].length <= 20words[i]consists of lowercase English letters.- All the strings of
wordsare unique.
Approach Overview
Problem Overview: You are given an array of strings and must build the shortest possible string that contains every word as a substring. Words can overlap, so the goal is to maximize overlaps between adjacent words while ensuring every string appears at least once.
Approach 1: Permutation and Greedy Overlap (O(n! · n · m), space O(n · m))
This brute-force method generates every permutation of the input words. For each ordering, compute the merged string by greedily overlapping adjacent words using the maximum suffix–prefix match. For example, if a ends with the same characters that b starts with, reuse that overlap instead of duplicating characters. Track the shortest merged result across all permutations. The approach is straightforward and demonstrates the core idea of overlap merging, but factorial growth makes it infeasible once n exceeds ~10.
Approach 2: Dynamic Programming with Bitmask (O(n^2 · 2^n + n^2 · m), space O(n · 2^n))
This is the optimal strategy. First compute pairwise overlaps between every pair of words, forming a weighted directed graph where the edge weight represents the additional characters needed when appending one word after another. Then apply dynamic programming with a bitmask representing which words are already used. The state dp[mask][i] stores the maximum overlap when the last chosen word is i. Iterate through masks and try appending unused words, updating overlaps efficiently. After filling the table, reconstruct the path that yields the largest overlap and build the final superstring. This converts the search space from factorial to 2^n, making it practical for typical constraints (n ≤ 12).
Approach 3: TSP-style Graph Formulation (O(n^2 · 2^n), space O(n · 2^n))
The problem can also be framed as a Traveling Salesman Problem on an overlap graph. Each word is a node, and the cost between nodes equals the number of extra characters required when concatenating them. The objective becomes finding a path that visits all nodes while minimizing total cost. A DP TSP implementation works almost identically to the bitmask approach, but the state stores minimal cost instead of maximum overlap. Heuristic versions sometimes use greedy edge selection to build a near-optimal ordering faster, though exact DP remains the most reliable for interviews.
Recommended for interviews: Start by explaining the permutation idea to show you understand overlap merging. Then move quickly to the DP + bitmask solution. Interviewers expect this formulation because it transforms the problem into a manageable subset DP similar to TSP. Mastery of string overlap preprocessing and bitmask transitions demonstrates strong algorithmic design.
Approach 1: Approach 1: Using Dynamic Programming (DP) and Bitmasking
This approach uses dynamic programming with bitmasking to explore all subsets of the strings. The dynamic programming state dp[mask][i] is the shortest superstring for the subset of words represented by the bitmask 'mask' ending with the 'i-th' string. By iterating through all possible states and updating them based on the previously computed states, we determine the shortest superstring that includes all words. The final superstring is constructed by backtracking through the computed states.
The Python solution calculates the maximum overlap for every pair of strings and uses dynamic programming to find the shortest superstring that can be constructed. Overlaps are computed once and stored in a 2D list "overlaps". The dp table keeps track of the optimal solution for every subset of strings represented by a bitmask, and backtracking on this table gives the final superstring.
Code
Python
Complexity
Time Complexity: O(n^2 * 2^n) where n is the number of words. This is because there are 2^n subsets and each subset operation can have O(n^2) complexity for managing overlaps.
Space Complexity: O(n * 2^n) for storing DP and path arrays.
Approach 2: Approach 2: Traveling Salesman Problem (TSP) Heuristic
This approach translates the problem into a variant of the Travelling Salesman Problem (TSP) where the cities correspond to the strings and the distances between them are the inverse of the overlap size. The solution can use heuristics to find a short path that visits all the 'cities' once, effectively creating the shortest superstring. Since exact TSP is NP-hard, approximation algorithms or heuristics can speed up finding a good solution.
This C++ solution uses a dynamical approach similar to TSP by using bitmasks to represent subsets of words. The overlap between strings is used to define "distances", and the algorithm tries to maximize the overlap, effectively minimizing the path length, or the resulting superstring length. The "cost" or path length is maximized by summing up the overlaps between consecutive elements in permutations.
Code
C++
Complexity
Time Complexity: O(n^2 * 2^n), where n is the number of strings. This is due to calculating overlaps for every pair and iterating over all subsets.
Space Complexity: O(n * 2^n) for storing DP tables.
Approach 3: Approach 1: Permutation and Greedy Overlap
This approach involves generating all permutations of the words and computing the shortest superstring by calculating overlaps greedily. We concatenate each pair of words in the permutation, reducing the length by maximizing the overlap between consecutive strings. This brute force method is feasible with a small number of words due to its factorial time complexity but ensures the optimal solution is found.
This C program defines a function shortestSuperstring that uses permutation and greedy approach to find the shortest superstring for the given array of words. The auxiliary function findOverlap calculates maximum overlap between two strings and constructs a new string by overlapping. The permute function generates permutations and keeps track of the shortest constructed superstring.
Complexity
Time Complexity: O(n! * len^2) where n is the number of words and len is the average length of words.
Space Complexity: O(n * len) for storing intermediate permutations and results.
Approach 4: Approach 2: Dynamic Programming and TSP
This approach models the problem using dynamic programming with a bitmask and Traveling Salesman Problem (TSP) style optimization. By representing used words as a bitmask, we systematically build the shortest superstring by adding each word while maximizing overlaps, applying dynamic programming to store and reuse results of subproblems.
This C solution applies dynamic programming and bitmasking to calculate the shortest superstring. The method constructs a graph where nodes represent words, and edges express overlaps. By treating the problem as a TSP, the dp array is used to store minimum path lengths, leveraging overlap calculations to optimize transitions.
Complexity
Time Complexity: O(n^2 * 2^n) due to combination of all subsets and pairwise overlaps.
Space Complexity: O(n * 2^n) for dp and parent tracking arrays.
Approach 5: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Using Dynamic Programming (DP) and Bitmasking | Time Complexity: O(n^2 * 2^n) where n is the number of words. This is because there are 2^n subsets and each subset operation can have O(n^2) complexity for managing overlaps. |
| Approach 2: Traveling Salesman Problem (TSP) Heuristic | Time Complexity: O(n^2 * 2^n), where n is the number of strings. This is due to calculating overlaps for every pair and iterating over all subsets. |
| Approach 1: Permutation and Greedy Overlap | Time Complexity: O(n! * len^2) where n is the number of words and len is the average length of words. |
| Approach 2: Dynamic Programming and TSP | Time Complexity: O(n^2 * 2^n) due to combination of all subsets and pairwise overlaps. |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Permutation + Greedy Overlap | O(n! · n · m) | O(n · m) | Understanding the core overlap idea or when n is extremely small |
| Dynamic Programming + Bitmask | O(n^2 · 2^n) | O(n · 2^n) | Optimal interview solution for n ≤ 12 |
| TSP Graph DP | O(n^2 · 2^n) | O(n · 2^n) | When modeling the problem as a shortest Hamiltonian path |
| Greedy TSP Heuristic | O(n^2 · m) | O(n^2) | Fast approximation when exact optimal result is not required |
Video Solution
花花酱 LeetCode 943. Find the Shortest Superstring - 刷题找工作 EP231 • Hua Hua • 11,747 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Find the Shortest Superstring easy or hard?
Find the Shortest Superstring Python/Java solution
How to solve Find the Shortest Superstring in O(n^2 · 2^n)?
What is the best approach for Find the Shortest Superstring?
Is Find the Shortest Superstring asked at Google/Amazon/Meta?
What data structure is used in Find the Shortest Superstring?
What is the time complexity of Find the Shortest Superstring?
Ready to solve this problem?
Practice Find the Shortest Superstring with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor