Find the Shortest Superstring - Video Solutions

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.