Shortest Common Superstring in JavaScript

Given a set of strings, the shortest common superstring problem asks for the shortest string that contains every one of them as a contiguous substring. It is NP-hard, so the interesting algorithms are approximations. Thirty-eight years after the conjecture that a simple greedy merge comes within twice the optimum, a paper of September 2026 proved a factor of two, for a different polynomial-time algorithm: A Polynomial-Time 2-Approximation for Shortest Common Superstring (external link, opens in a new tab), result 128 of OpenAI's openai/math, with its proof checked in Lean.

This repository implements that algorithm in JavaScript, beside the classic algorithms it is measured against, an exact solver for small inputs and a benchmark harness. It has no dependencies and needs Node 18 or newer; the 2-approximation alone is 1,215 lines of src/two-approx.js.

The algorithms

Greedy's 3.5 is Kaplan and Shafrir's bound (2005).

Using it

const { twoApprox, greedy, exact, solve } = require('./src');

twoApprox(['cde', 'abc', 'efg']);           // 'abcdefg'
solve(['cde', 'abc', 'efg']);
// { superstring: 'abcdefg', lowerBound: 7, fallback: false }

Every function takes an array of strings and returns a string. Empty strings, duplicates and strings contained in another are dropped first, and symbols are Unicode code points, so a surrogate pair is never split. solve also returns lowerBound, the lower bound W the algorithm proves on the optimum. The answer is never longer than 2W, so W also says how far any answer can be from the best.

npm test               # every algorithm on 1,200 random instances
npm run bench          # the full benchmark, about 30 seconds; writes results/
npm run bench:quick    # a tenth of the instances

How the 2-approximation works

Every distinct substring of the inputs, the empty word included, is a vertex of a graph. An up edge appends a letter and costs one, a down edge deletes the first letter and costs nothing, and an Euler tour from the empty word spells a superstring as long as its number of up edges. For every substring the algorithm computes, longest first, a count of occurrences that no common superstring can undercut, with a rule for periodic words. The one-letter counts sum to the lower bound W, and they define a balanced graph with W up edges.

That graph is split into closed walks, and the walks with the same periodic text are rearranged into layers that each go round one period. A layer of period p gets an extra budget of p, the budgets sum to W, and the layers are connected to the empty word within those budgets. The Euler tour of the result has at most 2W letters. Two finishing steps can only shorten it: walks that connectivity turns out not to need are dropped, and leading or trailing letters are trimmed while every input still occurs.

The graph has one vertex per distinct substring, so time and memory grow with the square of the total input length. A thousand 40-letter reads take about 90 ms.

What the benchmark shows

The guarantee matters on inputs built to trap Greedy. On {c(ab)^k, (ba)^k, (ab)^k c}, Greedy, MGREEDY and TGREEDY all write 4k + 2 letters against an optimum of 2k + 4; the 2-approximation writes 2k + 6:

On ordinary inputs the picture is different. The benchmark generates four families (random strings over 4 and 26 letters, reads of a random genome, and strings cut from repetitions of a few short seeds), measures small instances against the exact optimum and large ones against W. On an Apple M4 Max, with Node 26.8.2, on 7 October 2026:

• On average, Greedy is usually better. Its mean ratio is better in seven of the eight families, and on small genome-read instances it is optimal 98% of the time, against 74%. The two exceptions: on 200 random 4-letter strings the 2-approximation wrote exactly W letters every time, which is provably optimal, and on small 4-letter instances it found the optimum more often (91% against 85%), despite a slightly worse mean.
• It is not faster. It is about ten times slower on small inputs, and over a hundred times slower on 60 periodic strings (16.30 ms against 0.127 ms). It wins on 1,000 genome reads (86 ms against 271 ms) only because the greedy here computes all pairwise overlaps; a suffix-tree Greedy runs in near-linear time.
• The lower bound is tight on easy inputs. W averages 0.97 to 1.00 of the optimum, so solve also certifies how close an answer is to the best.

The tests check every algorithm for a valid superstring on 1,200 random instances, and the 2-approximation for W ≤ OPT and length ≤ 2W. The full tables are in the repository's results/RESULTS.md.

Source

• bkarak/shortest-superstring-js (external link, opens in a new tab) (MIT)
• The account of the paper and the measurements: Shortest common superstring: the factor of two, measured