Shortest Superstring asks you to glue a set of strings into the shortest single string that contains every one of them. The exact answer is famously NP-hard, but a simple greedy merge gets you a good — and interview-friendly — solution: always combine the two strings that share the most letters.
Problem. Given a list of strings words, return the shortest string that contains every word in
words as a substring. (The greedy version below builds a short superstring by repeatedly merging the
most-overlapping pair.)
Example: words = ["cat", "atom", "omni"] → "catomni" (it contains cat, atom, and omni).
The slow way first
The brute-force answer tries every ordering of the words and overlaps adjacent ones, keeping the shortest result. With n words that is n! orderings — fine for 3 words, hopeless for 12. Even the optimal dynamic-programming version is exponential, because the problem is NP-hard.
The question to ask: can I make one good local decision at a time instead of searching all orderings? Greedy says yes — at each step, merge the pair that saves the most characters.
The idea: merge the biggest overlap, repeat
Keep a pool of strings. While more than one remains, scan every ordered pair (i, j) and compute the overlap — how many characters at the end of pool[i] match the start of pool[j]. Take the pair with the largest overlap, glue them on that shared piece, and put the merged string back in the pool. Repeat until a single string is left.
The key insight: merging the largest overlap removes the most redundant characters this round, which greedily keeps the running superstring short.
Walk through it
Step through the animation. We start with cat, atom, omni. The first round finds that cat and atom share at, so they merge into catom. The pool shrinks. The next round finds catom and omni share om, merging into catomni. One string is left, so that is the answer.
Pseudocode
pool = list of words
while more than one string in pool:
find the ordered pair (i, j) with the largest overlap
overlap = chars at end of pool[i] matching start of pool[j]
merged = pool[i] + pool[j] with the shared part written once
pool = [merged] + everything except pool[i] and pool[j]
return the single remaining stringThe Python solution
def shortest_superstring(words):
pool = list(words)
while len(pool) > 1:
best_i, best_j, best_overlap = 0, 1, -1
for i in range(len(pool)):
for j in range(len(pool)):
if i != j:
ov = overlap(pool[i], pool[j])
if ov > best_overlap:
best_i, best_j, best_overlap = i, j, ov
merged = merge(pool[best_i], pool[best_j], best_overlap)
pool = [merged] + [w for k, w in enumerate(pool)
if k != best_i and k != best_j]
return pool[0]poolstarts as a copy of the input words; it shrinks by one each round.- The double loop scores every ordered pair, tracking the largest overlap in
best_overlap. overlap(a, b)returns how many characters at the end ofaequal the start ofb.merge(a, b, ov)isa + b[ov:]— appendbbut skip the shared prefix.- We rebuild
poolas the merged string plus everything that was not merged. - When one string is left, the loop ends and we return it.
Complexity
| Case | Time | Notes |
|---|---|---|
| Try every ordering | O(n! · L) (moderate) | exact but exponential |
| Greedy merge (this solution) | O(n³ · L) (moderate) | n rounds, n² pairs, L to score |
O(n · L) (moderate)Here n is the number of words and L the longest string length. Greedy is not guaranteed optimal, but it is polynomial and usually very close — a great answer when an interviewer admits the exact problem is NP-hard.
When this pattern shows up
When the optimal solution is exponential (orderings, subsets, the traveling-salesman family), pitch a greedy that makes the best local choice each round. Scoring pairs and merging the best one is the same move behind Huffman coding and agglomerative clustering.
Overlap is directional: the end of a matching the start of b is not the same as the end of b
matching the start of a. Score both (i, j) and (j, i), which is why the inner loop checks every
ordered pair, not just i < j.
Practice
Starting from ['cat', 'atom', 'omni'], which pair merges first and what do they become?
1. What does the greedy step pick on each round?
2. How is the merge of a and b built when they overlap by ov characters?
3. Why does the inner loop consider both (i, j) and (j, i)?
4. Is the greedy answer always the truly shortest superstring?