Find the Shortest Superstring

Problem

Given an array of strings words, return the smallest string that contains each string in words as a substring. If there are multiple valid strings of the smallest length, return any of them.

You may assume that no string in words is a substring of another string in words.

Examples

Example 1

Input: words = ["alex","loves","leetcode"]
Output: "alexlovesleetcode"
Explanation: All permutations of "alex","loves","leetcode" would also be accepted.

Example 2

Input: words = ["catg","ctaagt","gcta","ttca","atgcatc"]
Output: "gctaagttcatgcatc"

Constraints

• 1 <= words.length <= 12
• 1 <= words[i].length <= 20
• words[i] consists of lowercase English letters.
• All the strings of words are unique.

Solution

Method 1 – Brute Force (All Permutations)

Intuition

Try all possible orders of concatenating the strings, always merging with maximum possible overlap. The shortest result among all permutations is the answer. This is only feasible for small n (e.g., n ≤ 7).

Approach

1. Generate all permutations of the input strings.
2. For each permutation, merge the strings one by one, always overlapping as much as possible.
3. Track the minimum length found.
4. Return the minimum length or the actual string.

Code

Java

class Solution {
    public String shortestSuperstring(String[] words) {
        List<String> perms = new ArrayList<>();
        boolean[] used = new boolean[words.length];
        return permute(words, used, new ArrayList<>(), "");
    }

    private String permute(String[] words, boolean[] used, List<String> order, String best) {
        if (order.size() == words.length) {
            String merged = order.get(0);
            for (int i = 1; i < order.size(); i++) {
                merged = merge(merged, order.get(i));
            }
            if (best.equals("") || merged.length() < best.length()) return merged;
            return best;
        }
        for (int i = 0; i < words.length; i++) {
            if (!used[i]) {
                used[i] = true;
                order.add(words[i]);
                String candidate = permute(words, used, order, best);
                if (best.equals("") || candidate.length() < best.length()) best = candidate;
                order.remove(order.size() - 1);
                used[i] = false;
            }
        }
        return best;
    }

    private String merge(String a, String b) {
        int maxOverlap = 0;
        for (int k = Math.min(a.length(), b.length()); k > 0; k--) {
            if (a.endsWith(b.substring(0, k))) {
                maxOverlap = k;
                break;
            }
        }
        return a + b.substring(maxOverlap);
    }
}

Complexity

• ⏰ Time complexity: O(n! * n * L^2) where n is the number of strings and L is the average string length. This is due to checking all permutations and overlaps.
• 🧺 Space complexity: O(n * L) for storing permutations and intermediate strings.

Method 2 – DP with Bitmask (Traveling Salesman Style)

Intuition

We want to join all words together with as much overlap as possible. This is similar to the Traveling Salesman Problem, where each word is a city and the cost is the extra length needed to add a word after another. The brute force approach considers all permutations, but with DP and bitmasking, we can efficiently compute the optimal solution by storing, for every subset of words and every possible last word, the shortest superstring that covers that subset and ends with that word. This DP state captures the minimal superstring for each combination, allowing us to reuse solutions to overlapping subproblems and avoid redundant computation.

Detailed Reasoning

Suppose we have strings words = [s1, s2, s3, s4].

Now, one of the order of combinations can be, say Order 1 - [2,3,1,4], steps will be [s2+s3, s1, s4] –> [s2+s3+s1, s4] –> [s1+s2+s3+s4]. Similarly, order 2 = [1,3,2,4] can have steps - [s1+s3, s2, s4] –> [s1+s2+s3, s4] –> [s1+s2+s3+s4].

Note that, for both the orders, calculate the optimal solution for the subset [s1, s2, s3], which is reused in multiple permutations. This overlapping subproblem structure is ideal for DP. We use a bitmask to represent the set of strings included so far, and for each possible last string, we store the best result.

Formulation: dp[mask][i] = length of the shortest superstring for set of strings in mask, ending with string i.

Recurrence: dp[mask][i] = min(dp[prev_mask][j] + len(i) - overlap[j][i]) for all j ≠ i, where prev_mask is mask with the i-th bit unset.

This reduces the exponential number of permutations to O(n^2 * 2^n) states.

Approach

1. Compute the maximum overlap between every pair of words.
2. Use DP with bitmask: dp[mask][i] is the shortest superstring for set mask ending with word i.
3. For each state, try to append a new word maximizing overlap.
4. Reconstruct the answer from the DP table.

Code

C++

class Solution {
public:
    string shortestSuperstring(vector<string>& words) {
        int n = words.size();
        vector<vector<int>> overlap(n, vector<int>(n));
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j) if (i != j)
                for (int k = min(words[i].size(), words[j].size()); k > 0; --k)
                    if (words[i].substr(words[i].size()-k) == words[j].substr(0, k)) {
                        overlap[i][j] = k; break;
                    }
        vector<vector<int>> dp(1<<n, vector<int>(n, 0));
        vector<vector<int>> parent(1<<n, vector<int>(n, -1));
        for (int mask = 1; mask < (1<<n); ++mask) {
            for (int j = 0; j < n; ++j) {
                if (!(mask & (1<<j))) continue;
                int pmask = mask ^ (1<<j);
                if (pmask == 0) continue;
                for (int i = 0; i < n; ++i) {
                    if (!(pmask & (1<<i))) continue;
                    int val = dp[pmask][i] + overlap[i][j];
                    if (val > dp[mask][j]) {
                        dp[mask][j] = val;
                        parent[mask][j] = i;
                    }
                }
            }
        }
        int mask = (1<<n)-1, last = 0, best = -1;
        for (int i = 0; i < n; ++i)
            if (dp[mask][i] > best) { best = dp[mask][i]; last = i; }
        vector<int> path;
        while (last != -1) {
            path.push_back(last);
            int tmp = parent[mask][last];
            mask ^= (1<<last);
            last = tmp;
        }
        reverse(path.begin(), path.end());
        vector<bool> seen(n);
        string ans = words[path[0]];
        seen[path[0]] = true;
        for (int k = 1; k < path.size(); ++k) {
            int i = path[k-1], j = path[k];
            ans += words[j].substr(overlap[i][j]);
            seen[j] = true;
        }
        for (int i = 0; i < n; ++i) if (!seen[i]) ans += words[i];
        return ans;
    }
};

Go

func shortestSuperstring(words []string) string {
    n := len(words)
    overlap := make([][]int, n)
    for i := range overlap {
        overlap[i] = make([]int, n)
        for j := range overlap[i] {
            if i == j { continue }
            for k := min(len(words[i]), len(words[j])); k > 0; k-- {
                if words[i][len(words[i])-k:] == words[j][:k] {
                    overlap[i][j] = k; break
                }
            }
        }
    }
    dp := make([][]int, 1<<n)
    parent := make([][]int, 1<<n)
    for i := range dp {
        dp[i] = make([]int, n)
        parent[i] = make([]int, n)
        for j := range parent[i] { parent[i][j] = -1 }
    }
    for mask := 1; mask < 1<<n; mask++ {
        for j := 0; j < n; j++ {
            if mask&(1<<j) == 0 { continue }
            pmask := mask ^ (1<<j)
            if pmask == 0 { continue }
            for i := 0; i < n; i++ {
                if pmask&(1<<i) == 0 { continue }
                val := dp[pmask][i] + overlap[i][j]
                if val > dp[mask][j] {
                    dp[mask][j] = val
                    parent[mask][j] = i
                }
            }
        }
    }
    mask, last, best := (1<<n)-1, 0, -1
    for i := 0; i < n; i++ {
        if dp[mask][i] > best { best = dp[mask][i]; last = i }
    }
    path := []int{}
    for last != -1 {
        path = append(path, last)
        tmp := parent[mask][last]
        mask ^= 1 << last
        last = tmp
    }
    for i, j := 0, len(path)-1; i < j; i, j = i+1, j-1 {
        path[i], path[j] = path[j], path[i]
    }
    seen := make([]bool, n)
    ans := words[path[0]]
    seen[path[0]] = true
    for k := 1; k < len(path); k++ {
        i, j := path[k-1], path[k]
        ans += words[j][overlap[i][j]:]
        seen[j] = true
    }
    for i := 0; i < n; i++ {
        if !seen[i] { ans += words[i] }
    }
    return ans
}
func min(a, b int) int { if a < b { return a }; return b }

Java

class Solution {
    public String shortestSuperstring(String[] words) {
        int n = words.length;
        int[][] overlap = new int[n][n];
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j) if (i != j)
                for (int k = Math.min(words[i].length(), words[j].length()); k > 0; --k)
                    if (words[i].endsWith(words[j].substring(0, k))) {
                        overlap[i][j] = k; break;
                    }
        int[][] dp = new int[1<<n][n];
        int[][] parent = new int[1<<n][n];
        for (int[] row : parent) Arrays.fill(row, -1);
        for (int mask = 1; mask < (1<<n); ++mask) {
            for (int j = 0; j < n; ++j) {
                if ((mask & (1<<j)) == 0) continue;
                int pmask = mask ^ (1<<j);
                if (pmask == 0) continue;
                for (int i = 0; i < n; ++i) {
                    if ((pmask & (1<<i)) == 0) continue;
                    int val = dp[pmask][i] + overlap[i][j];
                    if (val > dp[mask][j]) {
                        dp[mask][j] = val;
                        parent[mask][j] = i;
                    }
                }
            }
        }
        int mask = (1<<n)-1, last = 0, best = -1;
        for (int i = 0; i < n; ++i)
            if (dp[mask][i] > best) { best = dp[mask][i]; last = i; }
        List<Integer> path = new ArrayList<>();
        while (last != -1) {
            path.add(last);
            int tmp = parent[mask][last];
            mask ^= (1<<last);
            last = tmp;
        }
        Collections.reverse(path);
        boolean[] seen = new boolean[n];
        StringBuilder ans = new StringBuilder(words[path.get(0)]);
        seen[path.get(0)] = true;
        for (int k = 1; k < path.size(); ++k) {
            int i = path.get(k-1), j = path.get(k);
            ans.append(words[j].substring(overlap[i][j]));
            seen[j] = true;
        }
        for (int i = 0; i < n; ++i) if (!seen[i]) ans.append(words[i]);
        return ans.toString();
    }
}

Kotlin

class Solution {
    fun shortestSuperstring(words: Array<String>): String {
        val n = words.size
        val overlap = Array(n) { IntArray(n) }
        for (i in 0 until n)
            for (j in 0 until n) if (i != j)
                for (k in minOf(words[i].length, words[j].length) downTo 1)
                    if (words[i].endsWith(words[j].substring(0, k))) {
                        overlap[i][j] = k; break
                    }
        val dp = Array(1 shl n) { IntArray(n) }
        val parent = Array(1 shl n) { IntArray(n) { -1 } }
        for (mask in 1 until (1 shl n)) {
            for (j in 0 until n) {
                if (mask and (1 shl j) == 0) continue
                val pmask = mask xor (1 shl j)
                if (pmask == 0) continue
                for (i in 0 until n) {
                    if (pmask and (1 shl i) == 0) continue
                    val v = dp[pmask][i] + overlap[i][j]
                    if (v > dp[mask][j]) {
                        dp[mask][j] = v
                        parent[mask][j] = i
                    }
                }
            }
        }
        var mask = (1 shl n) - 1
        var last = 0
        var best = -1
        for (i in 0 until n) if (dp[mask][i] > best) { best = dp[mask][i]; last = i }
        val path = mutableListOf<Int>()
        while (last != -1) {
            path.add(last)
            val tmp = parent[mask][last]
            mask = mask xor (1 shl last)
            last = tmp
        }
        path.reverse()
        val seen = BooleanArray(n)
        val ans = StringBuilder(words[path[0]])
        seen[path[0]] = true
        for (k in 1 until path.size) {
            val i = path[k-1]; val j = path[k]
            ans.append(words[j].substring(overlap[i][j]))
            seen[j] = true
        }
        for (i in 0 until n) if (!seen[i]) ans.append(words[i])
        return ans.toString()
    }
}

Python

class Solution:
    def shortestSuperstring(self, words: list[str]) -> str:
        n = len(words)
        overlap = [[0]*n for _ in range(n)]
        for i in range(n):
            for j in range(n):
                if i == j: continue
                for k in range(min(len(words[i]), len(words[j])), 0, -1):
                    if words[i][-k:] == words[j][:k]:
                        overlap[i][j] = k
                        break
        dp = [[0]*n for _ in range(1<<n)]
        parent = [[-1]*n for _ in range(1<<n)]
        for mask in range(1, 1<<n):
            for j in range(n):
                if not (mask & (1<<j)): continue
                pmask = mask ^ (1<<j)
                if pmask == 0: continue
                for i in range(n):
                    if not (pmask & (1<<i)): continue
                    val = dp[pmask][i] + overlap[i][j]
                    if val > dp[mask][j]:
                        dp[mask][j] = val
                        parent[mask][j] = i
        mask, last, best = (1<<n)-1, 0, -1
        for i in range(n):
            if dp[mask][i] > best:
                best = dp[mask][i]
                last = i
        path = []
        while last != -1:
            path.append(last)
            tmp = parent[mask][last]
            mask ^= (1<<last)
            last = tmp
        path = path[::-1]
        seen = [False]*n
        ans = words[path[0]]
        seen[path[0]] = True
        for k in range(1, len(path)):
            i, j = path[k-1], path[k]
            ans += words[j][overlap[i][j]:]
            seen[j] = True
        for i in range(n):
            if not seen[i]: ans += words[i]
        return ans

Rust

impl Solution {
    pub fn shortest_superstring(words: Vec<String>) -> String {
        let n = words.len();
        let mut overlap = vec![vec![0; n]; n];
        for i in 0..n {
            for j in 0..n {
                if i == j { continue; }
                for k in (1..=words[i].len().min(words[j].len())).rev() {
                    if &words[i][words[i].len()-k..] == &words[j][..k] {
                        overlap[i][j] = k;
                        break;
                    }
                }
            }
        }
        let mut dp = vec![vec![0; n]; 1<<n];
        let mut parent = vec![vec![-1; n]; 1<<n];
        for mask in 1..1<<n {
            for j in 0..n {
                if mask & (1<<j) == 0 { continue; }
                let pmask = mask ^ (1<<j);
                if pmask == 0 { continue; }
                for i in 0..n {
                    if pmask & (1<<i) == 0 { continue; }
                    let val = dp[pmask][i] + overlap[i][j];
                    if val > dp[mask][j] {
                        dp[mask][j] = val;
                        parent[mask][j] = i as i32;
                    }
                }
            }
        }
        let (mut mask, mut last, mut best) = ((1<<n)-1, 0, -1);
        for i in 0..n {
            if dp[mask][i] > best { best = dp[mask][i]; last = i; }
        }
        let mut path = vec![];
        while last != -1 {
            path.push(last);
            let tmp = parent[mask][last];
            mask ^= 1 << last;
            last = if tmp == -1 { -1 } else { tmp as usize };
        }
        path.reverse();
        let mut seen = vec![false; n];
        let mut ans = words[path[0]].clone();
        seen[path[0]] = true;
        for k in 1..path.len() {
            let i = path[k-1]; let j = path[k];
            ans += &words[j][overlap[i][j]..];
            seen[j] = true;
        }
        for i in 0..n { if !seen[i] { ans += &words[i]; } }
        ans
    }
}

TypeScript

class Solution {
    shortestSuperstring(words: string[]): string {
        const n = words.length;
        const overlap = Array.from({length: n}, () => Array(n).fill(0));
        for (let i = 0; i < n; i++)
            for (let j = 0; j < n; j++) if (i !== j)
                for (let k = Math.min(words[i].length, words[j].length); k > 0; k--)
                    if (words[i].endsWith(words[j].slice(0, k))) {
                        overlap[i][j] = k; break;
                    }
        const dp = Array.from({length: 1<<n}, () => Array(n).fill(0));
        const parent = Array.from({length: 1<<n}, () => Array(n).fill(-1));
        for (let mask = 1; mask < (1<<n); mask++) {
            for (let j = 0; j < n; j++) {
                if (!(mask & (1<<j))) continue;
                const pmask = mask ^ (1<<j);
                if (pmask === 0) continue;
                for (let i = 0; i < n; i++) {
                    if (!(pmask & (1<<i))) continue;
                    const val = dp[pmask][i] + overlap[i][j];
                    if (val > dp[mask][j]) {
                        dp[mask][j] = val;
                        parent[mask][j] = i;
                    }
                }
            }
        }
        let mask = (1<<n)-1, last = 0, best = -1;
        for (let i = 0; i < n; i++)
            if (dp[mask][i] > best) { best = dp[mask][i]; last = i; }
        const path: number[] = [];
        while (last !== -1) {
            path.push(last);
            const tmp = parent[mask][last];
            mask ^= (1<<last);
            last = tmp;
        }
        path.reverse();
        const seen = Array(n).fill(false);
        let ans = words[path[0]];
        seen[path[0]] = true;
        for (let k = 1; k < path.length; k++) {
            const i = path[k-1], j = path[k];
            ans += words[j].slice(overlap[i][j]);
            seen[j] = true;
        }
        for (let i = 0; i < n; i++) if (!seen[i]) ans += words[i];
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(n^2 * 2^n + n^3) where n is the number of words. The DP has O(n*2^n) states, and overlap computation is O(n^3).
• 🧺 Space complexity: O(n*2^n) for DP and parent tables.