DP — Find the Shortest Superstring

↗ LeetCode: Find the Shortest Superstring · Hard · pattern chapter →

Asked atGoogleAmazon

Return shortest string containing every given word as substring.

Example 1 — words=["alex","loves","leetcode"] → "alexlovesleetcode" (no overlaps merge) Example 2 — words=["catg","ctaagt","gcta","ttca","atgcatc"] → "gctaagttcatgcatc" (heavy overlaps) Example 3 — words=["a"] → "a"

Constraints — 1 ≤ n ≤ 12; each word ≤ 20 chars. Brute permutation is O(n!·n·L) — 12!·12·20 ≈ 1.1·10¹¹ ops = TLE. Bitmask DP is O(n²·2ⁿ) ≤ 144·4096 = 6·10⁵ ops.

Progressive Hints

Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.

---

⏱️Interview timer00:00

Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.

Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.

Approach 1 — Brute permutation

Intuition. Try every ordering, concat with max overlap between adjacent pair. Return shortest. n! orderings.

Complexity — Time O(n!·n·L); Space O(n). TLE past n=9. In an interview say "orderings collapse under bitmask (visited-set, last-word) → classic TSP DP → O(n²·2ⁿ)."

---

Approach 2 — Bitmask TSP-style DP + overlap precompute (canonical)

Insight.

1. overlap[i][j] = max suffix of words[i] that is prefix of words[j].
2. dp[mask][i] = shortest length ending at word i after using set mask.
3. Reconstruct path via predecessor tracking.

String shortestSuperstring(String[] words) {
    int n = words.length;
    int[][] ov = new int[n][n];
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (i != j) ov[i][j] = computeOverlap(words[i], words[j]);
    int full = 1 << n;
    int[][] dp = new int[full][n];
    int[][] par = new int[full][n];
    for (int[] r : dp) Arrays.fill(r, Integer.MAX_VALUE / 2);
    for (int i = 0; i < n; i++) dp[1 << i][i] = words[i].length();
    for (int mask = 1; mask < full; mask++)
        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) == 0) continue;
            for (int j = 0; j < n; j++) {
                if ((mask & (1 << j)) != 0) continue;
                int cand = dp[mask][i] + words[j].length() - ov[i][j];
                int nMask = mask | (1 << j);
                if (cand < dp[nMask][j]) { dp[nMask][j] = cand; par[nMask][j] = i; }
            }
        }
    int last = 0;
    for (int i = 1; i < n; i++) if (dp[full-1][i] < dp[full-1][last]) last = i;
    int[] order = new int[n];
    int mask = full - 1;
    for (int k = n - 1; k >= 0; k--) { order[k] = last; int prev = par[mask][last]; mask ^= 1 << last; last = prev; }
    StringBuilder sb = new StringBuilder(words[order[0]]);
    for (int k = 1; k < n; k++) sb.append(words[order[k]].substring(ov[order[k-1]][order[k]]));
    return sb.toString();
}
int computeOverlap(String a, String b) {
    int max = Math.min(a.length(), b.length());
    for (int k = max; k > 0; k--) if (a.endsWith(b.substring(0, k))) return k;
    return 0;
}

Execution Trace

Bitmask TSP-style DP + overlap precompute (canonical)

Step 1 / 3Initialize scan.

Complexity — Time O(n² · 2ⁿ); Space O(n · 2ⁿ). Say aloud in an interview: "canonical bitmask-TSP — same skeleton as Shortest Path Visiting All Nodes."

---

Try it yourself

Complexity summary

Approach	Time	Space	Grade
Brute permutation	O(n!·n·L)	O(n)	TLE past n=9
Bitmask TSP DP	O(n² · 2ⁿ)	O(n · 2ⁿ)	Canonical

When to use which

• Small n TSP-style → bitmask DP.
• Approximation → greedy longest-overlap merge.

✨AI Study CompanionBeta

Related problems

• Shortest Path Visiting All Nodes

Was this page helpful?