A while back I wrote an introduction to the shortest superstring problem and promised two follow-ups: one showing the greedy algorithm I wrote in VBA, and another showing how I bolted optimization on top to do better than greedy alone. Then I did what I usually do with “future work” and let it sit. Here, finally, is that follow-up — the whole thing in one post, because this is really the story of how I solved the shortest superstring problem in Excel with two stages of the same machine: a VBA pass that generates candidates, and an optimization model that picks the best of them.
Quick refresher on the problem. You’re given a set of strings, and you want the shortest single string that contains all of them. “ABA” and “AAB” can overlap into “AABA” (four characters) by gluing the shared “A”. It sounds like a word puzzle; it’s actually NP-complete, which is math for “the honest algorithm takes longer than the heat death of the universe once the set gets big.” So you don’t chase the exact answer. You chase a good one, quickly. My tool for that — as with most of the models I’ve built for fun over the years — was Excel with a VBA layer and the free OpenSolver add-in.
Stage one: let VBA build the overlaps
The greedy idea behind superstrings is simple: find two strings that overlap a lot, merge them, and repeat. My VBA does a thorough version of that. For every pair of strings on the sheet, it looks for the largest overlap — the longest suffix of one that equals a prefix of the other — and writes the merged string into a new row, tagging it with which of the original strings it now contains. So “abrac” and “racad” (overlap “rac”) become “abracad”, labeled as covering s0 and s4.
One routine (I named it metralla — Spanish for shrapnel, because it sprays new strings everywhere) just runs that merge pass over and over until a full sweep produces nothing new. There’s also a guard, compCheck, that refuses to merge two candidates if they already cover the same original string — no point building “abracabrac”. When the dust settles I don’t have one greedy answer; I have a whole catalog of candidate merged strings, each one a legal partial superstring covering some subset of the originals. On the DNA-flavored test set, ten little strings exploded into a few thousand candidates. That explosion is the point.
The superstring VBA behind the merges
Since the whole point of this post is to actually show the thing, here’s the superstring VBA that does the work, trimmed to its core. First the merge loop — for each pair of strings it tries the biggest overlap first and, if the merge is worth keeping, writes it out with its coverage label:
Do While Cells(r, 1).Value <> ""
Do While Cells(r2, 3).Value <> ""
For ic = 1 To longest_string - 1
i = longest_string - ic ' try the biggest overlap first
If Right(Cells(r, 1), i) = Left(Cells(r2, 3), i) _
And Cells(r, 1) <> Cells(r2, 3) Then
' skip if the two pieces already share an original
If Not compCheck(Cells(r, 2), Cells(r2, 4)) Then
Cells(o, 3).Value = Cells(r, 1) & _
Right(Cells(r2, 3), Len(Cells(r2, 3)) - i)
Cells(o, 4).Value = Cells(r, 2) & " " & Cells(r2, 4)
o = o + 1
End If
End If
Next ic
r2 = r2 + 1
Loop
r = r + 1
LoopAnd the little helper that keeps it honest — compCheck returns true when two coverage labels already share an original string, which is how the merge loop avoids gluing two pieces that both already contain, say, s3:
Public Function compCheck(str1 As String, str2 As String) As Boolean
Dim item1 As Variant, item2 As Variant
compCheck = False
For Each item1 In Split(str1)
For Each item2 In Split(str2)
If item1 = item2 Then
compCheck = True
Exit Function
End If
Next
Next
End FunctionThat’s the honest heart of it. The real module has a bit more plumbing — a lookup so it doesn’t write the same merged string twice, and a pass that absorbs any string already sitting inside another — but the overlap-and-merge above is the engine, and metralla just calls it in a loop until nothing new appears.
Stage two: let the optimizer solve the shortest superstring problem
Here’s where I stopped being greedy and started being optimal — and where this model quietly stops being a pure “shortest superstring” solver and becomes something a bit smarter. Instead of trusting greedy’s single merged result, I hand the whole catalog of candidates to an integer program and ask: what’s the cheapest set of these strings that together covers every original?
That’s a weighted set-cover model, and it’s small to state. Give every candidate string a yes/no variable — include it or not. Build a coverage table (a wall of FIND formulas) marking which originals each candidate contains. Then:
minimize Σ lengthc · usec
subject to for every original string s: Σc contains s usec ≥ 1
where usec = 1 if candidate string c is chosen, 0 otherwise.
In words: every original has to be inside at least one string I pick, and among all the ways to do that, I want the one with the least total length. OpenSolver ships this off to the CBC solver and it comes back with the answer in a blink, because while there are thousands of candidates, the model itself is just one binary column and a handful of coverage rows. On the “abracadabra” set it picks a single ten-character string, “adabracada,” that swallows all five originals — you genuinely can’t do better than that.
The honest part: sometimes it hands you two strings
I want to be straight about what this model does and doesn’t do, because it surprised me the first time. On the harder DNA set, the optimizer didn’t return one superstring. It returned two — a 31-character piece and a 42-character piece, 73 characters between them — because forcing all ten strings into a single chain would have cost more. My objective was minimum total length, not minimum number of strings, so the solver is perfectly happy to hand back a small pile of strings if that’s cheaper than one long rope.
Depending on what you wanted, that’s either a bug or a feature. If you strictly need one string, this formulation is an approximation and you’d add a constraint to force a single piece (and pay for it in both length and solve time). But for the use I cared about — cover everything with as few total characters as possible — the set-cover version is arguably the more useful question, and it has the nice property of being provably optimal for the candidates I generated. Greedy alone would have committed to one chain early and never looked back; the optimizer gets to weigh the whole catalog at once.
Where this fits with the other models
If you’ve read my posts on building fantasy baseball lineups, this two-stage shape might feel familiar. Over there I used Hall’s marriage theorem and a greedy slotting trick to let a solver worry only about which players to pick; here a greedy pass builds candidates and the solver worries only about which to combine. Set cover and matching are cousins in the same family of “choose a subset that satisfies every requirement” problems, and the recurring move in all of it is the same: don’t make the optimizer enumerate an exponential universe — use a cheap heuristic to propose good pieces, then let the math pick the best combination of them. That division of labor is most of what twenty years of building these models has actually taught me.
The superstring request originally came to me, of all places, through Fiverr — a job that went nowhere but left me with a problem I couldn’t stop thinking about. That’s a fair trade in my book: I never got paid, and I got a spreadsheet I still open sometimes just to watch metralla spray strings across the screen.
Things that I use, like, and am affiliated with:
Mint Mobile offers great cell phone service for $15 flat, get $15 off using the link. Get discounted phones with service activation and no contract.
I never spend money before I check Mr Rebates or Rakuten to get cashbacks, rebates, discounts, coupons or cheaper gift cards.