Hardbitmask-dp
Find the Shortest Superstring
Problem (restated)
n ≤ 12 unique words. Return a shortest string that contains every word as a substring.
Intuition
A shortest superstring is a Hamiltonian path on the words. Edge i → j costs |j| - overlap(i,j), where overlap is the longest suffix of i that is a prefix of j. Drop any word contained in another first.
Approaches
TSP on overlap
UnverifiedTime O(n^2 * 2^n * L)Space O(n * 2^n)
Idea. dp[mask][last] = min length of a superstring of subset mask that starts with last. Glue last in front of a superstring of mask \ {last} starting at nxt. Iterate last then nxt; on equal length keep the smaller nxt. Reconstruct from the full-mask start of min length (ties → smallest index), walk parent, glue leftovers.
Walkthrough. ["alex","loves","leetcode"] → "alexlovesleetcode". ["catg","ctaagt","gcta","ttca","atgcatc"] → "gctaagttcatgcatc".
Trade-offs. The parent/tie rules are required so TS/PY/C# emit the same string among equally short answers. n=12, 2^n n^2 is fine.
Solution
export function shortestSuperstring(words: string[]): string {
const kept: string[] = [];
for (let i = 0; i < words.length; i++) {
const w = words[i]!;
let contained = false;
for (let j = 0; j < words.length; j++) {
if (i !== j && words[j]!.includes(w)) {
contained = true;
break;
}
}
if (!contained) kept.push(w);
}
words = kept;
const n = words.length;
if (n === 0) return "";
const ov: number[][] = Array.from({ length: n }, () => new Array<number>(n).fill(0));
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (i === j) continue;
const a = words[i]!, b = words[j]!;
const mx = Math.min(a.length, b.length);
for (let k = mx; k > 0; k--) {
if (a.slice(-k) === b.slice(0, k)) {
ov[i]![j] = k;
break;
}
}
}
}
const INF = 1e9;
const N = 1 << n;
const dp: number[][] = Array.from({ length: N }, () => new Array<number>(n).fill(INF));
const parent: number[][] = Array.from({ length: N }, () => new Array<number>(n).fill(-1));
for (let i = 0; i < n; i++) dp[1 << i]![i] = words[i]!.length;
for (let mask = 0; mask < N; mask++) {
for (let last = 0; last < n; last++) {
if ((mask & (1 << last)) === 0) continue;
const rest = mask ^ (1 << last);
if (rest === 0) continue;
for (let nxt = 0; nxt < n; nxt++) {
if ((rest & (1 << nxt)) === 0) continue;
const prev = dp[rest]![nxt]!;
if (prev >= INF) continue;
const nlen = words[last]!.length + prev - ov[last]![nxt]!;
const p = parent[mask]![last]!;
if (nlen < dp[mask]![last]! || (nlen === dp[mask]![last]! && (p < 0 || nxt < p))) {
dp[mask]![last] = nlen;
parent[mask]![last] = nxt;
}
}
}
}
const full = N - 1;
let best = 0;
for (let last = 1; last < n; last++) {
if (dp[full]![last]! < dp[full]![best]!) best = last;
}
const path: number[] = [];
let mask = full, cur = best;
while (cur >= 0) {
path.push(cur);
const nxt = parent[mask]![cur]!;
mask ^= 1 << cur;
cur = nxt;
}
let ans = words[path[0]!]!;
for (let i = 1; i < path.length; i++) {
const a = path[i - 1]!, b = path[i]!;
ans += words[b]!.slice(ov[a]![b]!);
}
return ans;
}
export function shortestSuperstring(words: string[]): string {
const kept: string[] = [];
for (let i = 0; i < words.length; i++) {
const w = words[i]!;
let contained = false;
for (let j = 0; j < words.length; j++) {
if (i !== j && words[j]!.includes(w)) {
contained = true;
break;
}
}
if (!contained) kept.push(w);
}
words = kept;
const n = words.length;
if (n === 0) return "";
const ov: number[][] = Array.from({ length: n }, () => new Array<number>(n).fill(0));
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (i === j) continue;
const a = words[i]!, b = words[j]!;
const mx = Math.min(a.length, b.length);
for (let k = mx; k > 0; k--) {
if (a.slice(-k) === b.slice(0, k)) {
ov[i]![j] = k;
break;
}
}
}
}
const INF = 1e9;
const N = 1 << n;
const dp: number[][] = Array.from({ length: N }, () => new Array<number>(n).fill(INF));
const parent: number[][] = Array.from({ length: N }, () => new Array<number>(n).fill(-1));
for (let i = 0; i < n; i++) dp[1 << i]![i] = words[i]!.length;
for (let mask = 0; mask < N; mask++) {
for (let last = 0; last < n; last++) {
if ((mask & (1 << last)) === 0) continue;
const rest = mask ^ (1 << last);
if (rest === 0) continue;
for (let nxt = 0; nxt < n; nxt++) {
if ((rest & (1 << nxt)) === 0) continue;
const prev = dp[rest]![nxt]!;
if (prev >= INF) continue;
const nlen = words[last]!.length + prev - ov[last]![nxt]!;
const p = parent[mask]![last]!;
if (nlen < dp[mask]![last]! || (nlen === dp[mask]![last]! && (p < 0 || nxt < p))) {
dp[mask]![last] = nlen;
parent[mask]![last] = nxt;
}
}
}
}
const full = N - 1;
let best = 0;
for (let last = 1; last < n; last++) {
if (dp[full]![last]! < dp[full]![best]!) best = last;
}
const path: number[] = [];
let mask = full, cur = best;
while (cur >= 0) {
path.push(cur);
const nxt = parent[mask]![cur]!;
mask ^= 1 << cur;
cur = nxt;
}
let ans = words[path[0]!]!;
for (let i = 1; i < path.length; i++) {
const a = path[i - 1]!, b = path[i]!;
ans += words[b]!.slice(ov[a]![b]!);
}
return ans;
}
Template connection
Open TSP: mask = used words, extra dimension = start of the remaining path, cost = length after overlap.
Reflection
dp[mask][last]is the shortest superstring of that subset that starts withlast.lastis glued in front of a continuation; the overlap shortens the added length.- The overlap is the suffix of the word you add against the prefix of the continuation. If one word contains the other, the added length can fall to 0.
- One word is itself. On an equal length, keep the smaller index in the parent. The state is
2**n * n**2.