943. Find the Shortest Superstring - Solution

Q: Is Find the Shortest Superstring easy or hard?

Find the Shortest Superstring is categorized as Hard. The challenge comes from recognizing that the problem reduces to a Traveling Salesman–style dynamic programming problem using bitmasks, combined with careful string overlap computation.

Q: Find the Shortest Superstring Python/Java solution

Most implementations compute overlaps, run DP with bitmask states, and store parent pointers to reconstruct the order. Python, Java, and C++ solutions typically follow the same structure: overlap preprocessing, subset DP iteration, then building the final string using the optimal ordering.

Q: How to solve Find the Shortest Superstring in O(n^2 · 2^n)?

First compute the overlap length between every pair of strings. Use a bitmask to represent which words are included and maintain dp[mask][i] for the best overlap when ending with word i. Transition by adding an unused word j and updating overlap using the precomputed matrix. After filling DP states, reconstruct the path that maximizes total overlap and build the final merged string.

Q: What is the best approach for Find the Shortest Superstring?

Dynamic Programming with bitmasking is the most reliable approach. Precompute overlaps between every pair of words and run subset DP where dp[mask][i] tracks the best overlap ending with word i. The algorithm runs in O(n^2 · 2^n) time and reconstructs the optimal ordering that produces the shortest superstring.

Q: Is Find the Shortest Superstring asked at Google/Amazon/Meta?

Shortest superstring style problems appear in interviews at companies like Google, Amazon, and Meta because they combine graph modeling with dynamic programming. The problem tests your ability to transform a string problem into a Traveling Salesman–style DP using bitmasks.

Q: What data structure is used in Find the Shortest Superstring?

The solution uses arrays or matrices to store pairwise overlaps, plus a DP table indexed by bitmask and last node. Bitmasks efficiently represent subsets of words, enabling transitions similar to Hamiltonian path or TSP dynamic programming.

Q: What is the time complexity of Find the Shortest Superstring?

The optimal DP + bitmask solution runs in O(n^2 · 2^n) time and O(n · 2^n) space, where n is the number of strings. Pairwise overlap preprocessing adds O(n^2 · m) where m is the average string length. Brute-force permutation solutions take O(n! · n · m) and are only feasible for very small inputs.

The 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.

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.

Approach overview

Problem Overview: You are given an array of strings and must build the shortest possible string that contains every word as a substring. Words can overlap, so the goal is to maximize overlaps between adjacent words while ensuring every string appears at least once.

Approach 1: Permutation and Greedy Overlap (O(n! · n · m), space O(n · m))

This brute-force method generates every permutation of the input words. For each ordering, compute the merged string by greedily overlapping adjacent words using the maximum suffix–prefix match. For example, if a ends with the same characters that b starts with, reuse that overlap instead of duplicating characters. Track the shortest merged result across all permutations. The approach is straightforward and demonstrates the core idea of overlap merging, but factorial growth makes it infeasible once n exceeds ~10.

Approach 2: Dynamic Programming with Bitmask (O(n^2 · 2^n + n^2 · m), space O(n · 2^n))

This is the optimal strategy. First compute pairwise overlaps between every pair of words, forming a weighted directed graph where the edge weight represents the additional characters needed when appending one word after another. Then apply dynamic programming with a bitmask representing which words are already used. The state dp[mask][i] stores the maximum overlap when the last chosen word is i. Iterate through masks and try appending unused words, updating overlaps efficiently. After filling the table, reconstruct the path that yields the largest overlap and build the final superstring. This converts the search space from factorial to 2^n, making it practical for typical constraints (n ≤ 12).

Approach 3: TSP-style Graph Formulation (O(n^2 · 2^n), space O(n · 2^n))

The problem can also be framed as a Traveling Salesman Problem on an overlap graph. Each word is a node, and the cost between nodes equals the number of extra characters required when concatenating them. The objective becomes finding a path that visits all nodes while minimizing total cost. A DP TSP implementation works almost identically to the bitmask approach, but the state stores minimal cost instead of maximum overlap. Heuristic versions sometimes use greedy edge selection to build a near-optimal ordering faster, though exact DP remains the most reliable for interviews.

Recommended for interviews: Start by explaining the permutation idea to show you understand overlap merging. Then move quickly to the DP + bitmask solution. Interviewers expect this formulation because it transforms the problem into a manageable subset DP similar to TSP. Mastery of string overlap preprocessing and bitmask transitions demonstrates strong algorithmic design.

Approach 1: Approach 1: Using Dynamic Programming (DP) and Bitmasking

This approach uses dynamic programming with bitmasking to explore all subsets of the strings. The dynamic programming state dp[mask][i] is the shortest superstring for the subset of words represented by the bitmask 'mask' ending with the 'i-th' string. By iterating through all possible states and updating them based on the previously computed states, we determine the shortest superstring that includes all words. The final superstring is constructed by backtracking through the computed states.

Python

def shortestSuperstring(words):
    n = len(words)

    # Calculate the overlap between two strings
    def get_overlap(a, b):
        max_overlap = 0
        for i in range(len(a)):
            if b.startswith(a[i:]):
                max_overlap = len(a) - i
                break
        return max_overlap
    
    overlaps = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if i != j:
                overlaps[i][j] = get_overlap(words[i], words[j])
    
    dp = [[0] * n for _ in range(1 << n)]
    path = [[-1] * n for _ in range(1 << n)]

    for mask in range(1, 1 << n):
        for bit in range(n):
            if (mask >> bit) & 1:
                prev_mask = mask ^ (1 << bit)
                if prev_mask == 0:
                    continue
                for i in range(n):
                    if (prev_mask >> i) & 1:
                        value = dp[prev_mask][i] + overlaps[i][bit]
                        if value > dp[mask][bit]:
                            dp[mask][bit] = value
                            path[mask][bit] = i
    
    max_overlap = max(dp[-1])
    last = dp[-1].index(max_overlap)
    
    mask = (1 << n) - 1
    perm = []
    while last != -1:
        perm.append(last)
        temp = last
        last = path[mask][last]
        mask ^= (1 << temp)

    perm = perm[::-1]

    answer = words[perm[0]]
    for i in range(1, len(perm)):
        overlap_len = overlaps[perm[i - 1]][perm[i]]
        answer += words[perm[i]][overlap_len:]

    return answer

# Example usage
words = ["catg", "ctaagt", "gcta", "ttca", "atgcatc"]
print(shortestSuperstring(words))

The Python solution calculates the maximum overlap for every pair of strings and uses dynamic programming to find the shortest superstring that can be constructed. Overlaps are computed once and stored in a 2D list "overlaps". The dp table keeps track of the optimal solution for every subset of strings represented by a bitmask, and backtracking on this table gives the final superstring.

Complexity

Time Complexity: O(n^2 * 2^n) where n is the number of words. This is because there are 2^n subsets and each subset operation can have O(n^2) complexity for managing overlaps.
Space Complexity: O(n * 2^n) for storing DP and path arrays.

Try this approach in the editor

Approach 2: Approach 2: Traveling Salesman Problem (TSP) Heuristic

This approach translates the problem into a variant of the Travelling Salesman Problem (TSP) where the cities correspond to the strings and the distances between them are the inverse of the overlap size. The solution can use heuristics to find a short path that visits all the 'cities' once, effectively creating the shortest superstring. Since exact TSP is NP-hard, approximation algorithms or heuristics can speed up finding a good solution.

C++

#include <iostream>
#include <vector>
#include <string>
#include <limits.h>
using namespace std;

int calculate_overlap(string a, string b) {
    int max_overlap = 0;
    for (int i = 0; i < a.size(); ++i) {
        if (b.find(a.substr(i)) == 0) {
            max_overlap = a.size() - i;
            break;
        }
    }
    return max_overlap;
}

string shortestSuperstring(vector<string>& words) {
    int n = words.size();
    vector<vector<int>> overlaps(n, vector<int>(n, 0));

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i != j) {
                overlaps[i][j] = calculate_overlap(words[i], words[j]);
            }
        }
    }

    int max_mask = 1 << n;
    vector<vector<int>> dp(max_mask, vector<int>(n, 0));
    vector<vector<int>> parent(max_mask, vector<int>(n, -1));

    for (int mask = 1; mask < max_mask; ++mask) {
        for (int u = 0; u < n; ++u) {
            if ((mask & (1 << u)) == 0) continue;
            int prev_mask = mask ^ (1 << u);

            if (prev_mask == 0) continue;

            for (int v = 0; v < n; ++v) {
                if ((prev_mask & (1 << v)) == 0) continue;
                int val = dp[prev_mask][v] + overlaps[v][u];
                if (val > dp[mask][u]) {
                    dp[mask][u] = val;
                    parent[mask][u] = v;
                }
            }
        }
    }

    int max_overlap = 0, last = 0;
    for (int i = 0; i < n; ++i) {
        if (dp[max_mask - 1][i] > max_overlap) {
            max_overlap = dp[max_mask - 1][i];
            last = i;
        }
    }

    vector<int> perm;
    int mask = max_mask - 1;
    while (last != -1) {
        perm.push_back(last);
        int temp = last;
        last = parent[mask][last];
        mask ^= (1 << temp);
    }

    reverse(perm.begin(), perm.end());

    string result = words[perm[0]];
    for (int i = 1; i < perm.size(); ++i) {
        int overlap_len = overlaps[perm[i - 1]][perm[i]];
        result += words[perm[i]].substr(overlap_len);
    }

    return result;
}

int main() {
    vector<string> words = {"catg", "ctaagt", "gcta", "ttca", "atgcatc"};
    cout << shortestSuperstring(words) << endl;
    return 0;
}

This C++ solution uses a dynamical approach similar to TSP by using bitmasks to represent subsets of words. The overlap between strings is used to define "distances", and the algorithm tries to maximize the overlap, effectively minimizing the path length, or the resulting superstring length. The "cost" or path length is maximized by summing up the overlaps between consecutive elements in permutations.

Complexity

Time Complexity: O(n^2 * 2^n), where n is the number of strings. This is due to calculating overlaps for every pair and iterating over all subsets.
Space Complexity: O(n * 2^n) for storing DP tables.

Try this approach in the editor

Approach 3: Approach 1: Permutation and Greedy Overlap

This approach involves generating all permutations of the words and computing the shortest superstring by calculating overlaps greedily. We concatenate each pair of words in the permutation, reducing the length by maximizing the overlap between consecutive strings. This brute force method is feasible with a small number of words due to its factorial time complexity but ensures the optimal solution is found.

Python

from itertools import permutations


def find_overlap(a, b):
    max_overlap = 0
    len1, len2 = len(a), len(b)
    for i in range(1, min(len1, len2) + 1):
        if a[-i:] == b[:i]:
            max_overlap = i
    return a + b[max_overlap:]


def shortest_superstring(words):
    min_superstr = None

    for perm in permutations(words):
        superstring = perm[0]
        for i in range(1, len(perm)):
            superstring = find_overlap(superstring, perm[i])

        if min_superstr is None or len(superstring) < len(min_superstr):
            min_superstr = superstring

    return min_superstr


# Test
words = ["alex", "loves", "leetcode"]
print(shortest_superstring(words))

Java

import java.util.Arrays;

public class ShortestSuperstring {
    private static void findOverlap(String a, String b, StringBuilder res) {
        int maxOverlap = 0;
        int len1 = a.length(), len2 = b.length();
        for (int i = 1; i <= len1 && i <= len2; i++) {
            if (a.regionMatches(len1 - i, b, 0, i)) {
                maxOverlap = i;
            }
        }
        res.append(a.substring(0, len1 - maxOverlap)).append(b);
    }

    private static void permute(String[] words, boolean[] used, int depth, StringBuilder superStr, StringBuilder minSuperStr) {
        if (superStr.length() >= minSuperStr.length()) return;

        if (depth == words.length) {
            if (superStr.length() < minSuperStr.length()) {
                minSuperStr.setLength(0);
                minSuperStr.append(superStr);
            }
            return;
        }

        for (int i = 0; i < words.length; i++) {
            if (!used[i]) {
                used[i] = true;

                int originalLength = superStr.length();
                if (superStr.length() == 0) {
                    superStr.append(words[i]);
                } else {
                    StringBuilder temp = new StringBuilder();
                    findOverlap(superStr.toString(), words[i], temp);
                    superStr.setLength(0);
                    superStr.append(temp);
                }

                permute(words, used, depth + 1, superStr, minSuperStr);
                superStr.setLength(originalLength);

                used[i] = false;
            }
        }
    }

    public static String shortestSuperstring(String[] words) {
        StringBuilder minSuperStr = new StringBuilder();
        Arrays.stream(words).forEach(minSuperStr::append);
        boolean[] used = new boolean[words.length];

        permute(words, used, 0, new StringBuilder(), minSuperStr);

        return minSuperStr.toString();
    }

    public static void main(String[] args) {
        String[] words = {"alex", "loves", "leetcode"};
        System.out.println(shortestSuperstring(words));
    }
}

C++

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

void findOverlap(const string &a, const string &b, string &res) {
    int maxOverlap = 0;
    int len1 = a.length(), len2 = b.length();
    for (int i = 1; i <= len1 && i <= len2; i++) {
        if (a.compare(len1 - i, i, b, 0, i) == 0) {
            maxOverlap = i;
        }
    }
    res = a.substr(0, len1 - maxOverlap) + b;
}

void permute(const vector<string> &words, int depth, vector<bool> &used, string superStr, string &minSuperStr, int &minLen) {
    if (superStr.length() >= minLen) return;

    if (depth == words.size()) {
        if (superStr.length() < minLen) {
            minLen = superStr.length();
            minSuperStr = superStr;
        }
        return;
    }

    for (int i = 0; i < words.size(); i++) {
        if (!used[i]) {
            used[i] = true;

            if (superStr.empty()) {
                permute(words, depth + 1, used, words[i], minSuperStr, minLen);
            } else {
                string temp;
                findOverlap(superStr, words[i], temp);
                permute(words, depth + 1, used, temp, minSuperStr, minLen);
            }

            used[i] = false;
        }
    }
}

string shortestSuperstring(vector<string> &words) {
    string minSuperStr;
    int minLen = INT_MAX;
    vector<bool> used(words.size(), false);

    permute(words, 0, used, "", minSuperStr, minLen);

    return minSuperStr;
}

int main() {
    vector<string> words = {"alex","loves","leetcode"};
    cout << shortestSuperstring(words) << endl;

    return 0;
}

JavaScript

function findOverlap(a, b) {
    let maxOverlap = 0;
    const len1 = a.length, len2 = b.length;
    for (let i = 1; i <= len1 && i <= len2; i++) {
        if (a.endsWith(b.substring(0, i))) {
            maxOverlap = i;
        }
    }
    return a + b.substring(maxOverlap);
}

function shortestSuperstring(words) {
    let minSuperStr = null;

    function permute(perm, unused) {
        if (unused.length === 0) {
            const superstring = perm.reduce((acc, word) => findOverlap(acc, word), "");
            if (!minSuperStr || superstring.length < minSuperStr.length) {
                minSuperStr = superstring;
            }
            return;
        }

        for (let i = 0; i < unused.length; i++) {
            permute([...perm, unused[i]], unused.slice(0, i).concat(unused.slice(i + 1)));
        }
    }
    
    permute([], words);

    return minSuperStr;
}

console.log(shortestSuperstring(["alex", "loves", "leetcode"]));

#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#define MAX 12

bool used[MAX];
char result[255];

void findOverlap(char *a, char *b, char *res) {
    int maxOverlap = 0;
    int len1 = strlen(a), len2 = strlen(b);
    for (int i = 1; i <= len1 && i <= len2; i++) {
        if (strncmp(a + len1 - i, b, i) == 0) {
            maxOverlap = i;
        }
    }
    sprintf(res, "%.*s%s", len1 - maxOverlap, a, b);
}

void permute(char words[][21], int n, char superStr[255], int len, char minSuperStr[255], int *minLen) {
    if (len >= *minLen) return;
    
    bool allUsed = true;
    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            allUsed = false;
            used[i] = true;

            if (len == 0) {
                strcpy(superStr, words[i]);
                permute(words, n, superStr, strlen(words[i]), minSuperStr, minLen);
            } else {
                char temp[255];
                findOverlap(superStr, words[i], temp);
                int tempLen = strlen(temp);
                permute(words, n, temp, tempLen, minSuperStr, minLen);
            }
            
            used[i] = false;
        }
    }
    if (allUsed && len < *minLen) {
        *minLen = len;
        strcpy(minSuperStr, superStr);
    }
}

char *shortestSuperstring(char words[][21], int wordsSize) {
    char minSuperStr[255];
    int minLen = 1000;
    memset(used, false, sizeof(used));

    permute(words, wordsSize, result, 0, minSuperStr, &minLen);

    return strdup(minSuperStr);
}

int main() {
    char words[][21] = {"alex","loves","leetcode"};
    int wordsSize = sizeof(words) / sizeof(words[0]);

    printf("%s\n", shortestSuperstring(words, wordsSize));
    return 0;
}

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string FindOverlap(string a, string b)
    {
        int maxOverlap = 0;
        int len1 = a.Length, len2 = b.Length;
        for (int i = 1; i <= len1 && i <= len2; i++)
        {
            if (a.Substring(len1 - i, i) == b.Substring(0, i))
            {
                maxOverlap = i;
            }
        }
        return a.Substring(0, len1 - maxOverlap) + b;
    }

    static void Permute(string[] words, bool[] used, int depth, ref string superStr, ref string minSuperStr)
    {
        if (superStr.Length >= minSuperStr.Length) return;

        if (depth == words.Length)
        {
            if (superStr.Length < minSuperStr.Length)
            {
                minSuperStr = superStr;
            }
            return;
        }

        for (int i = 0; i < words.Length; i++)
        {
            if (!used[i])
            {
                used[i] = true;

                string originalSuperStr = superStr;
                if (superStr.Length == 0)
                {
                    superStr = words[i];
                }
                else
                {
                    superStr = FindOverlap(superStr, words[i]);
                }

                Permute(words, used, depth + 1, ref superStr, ref minSuperStr);
                superStr = originalSuperStr;

                used[i] = false;
            }
        }
    }

    public static string ShortestSuperstring(string[] words)
    {
        string minSuperStr = string.Join("", words);
        string superStr = "";
        bool[] used = new bool[words.Length];

        Permute(words, used, 0, ref superStr, ref minSuperStr);

        return minSuperStr;
    }

    static void Main()
    {
        string[] words = { "alex", "loves", "leetcode" };
        Console.WriteLine(ShortestSuperstring(words));
    }
}

The Python solution uses the itertools's permutations to evaluate each possible arrangement of strings, merging them with maximum overlap using find_overlap. Each permutation yields a potential superstring, and the shortest found is returned after all are evaluated.

Complexity

Time Complexity: O(n! * len^2) due to factorial permutations and overlap calculations.
Space Complexity: O(n * len) for storing intermediate superstring results.

Try this approach in the editor

Approach 4: Approach 2: Dynamic Programming and TSP

This approach models the problem using dynamic programming with a bitmask and Traveling Salesman Problem (TSP) style optimization. By representing used words as a bitmask, we systematically build the shortest superstring by adding each word while maximizing overlaps, applying dynamic programming to store and reuse results of subproblems.

Python

def calculate_overlap(a, b):
    max_overlap = 0
    len1, len2 = len(a), len(b)
    for i in range(1, min(len1, len2) + 1):
        if a[-i:] == b[:i]:
            max_overlap = i
    return max_overlap


def shortest_superstring(words):
    n = len(words)
    overlap = [[0] * n for _ in range(n)]

    for i in range(n):
        for j in range(n):
            overlap[i][j] = calculate_overlap(words[i], words[j])

    dp = [[float('inf')] * n for _ in range(1 << n)]
    parent = [[-1] * n for _ in range(1 << n)]

    for i in range(n):
        dp[1 << i][i] = len(words[i])

    for mask in range(1 << n):
        for i in range(n):
            if mask & (1 << i):
                for j in range(n):
                    if i != j and mask & (1 << j):
                        currLen = dp[mask ^ (1 << i)][j] + len(words[i]) - overlap[j][i]
                        if currLen < dp[mask][i]:
                            dp[mask][i] = currLen
                            parent[mask][i] = j

    mask = (1 << n) - 1
    last = min(range(n), key=lambda i: dp[mask][i])
    minLength = dp[mask][last]

    path = []
    while mask:
        path.append(last)
        temp = parent[mask][last]
        mask ^= 1 << last
        last = temp

    path.reverse()
    superstring = words[path[0]]

    for i in range(1, len(path)):
        j = path[i]
        overlap_len = overlap[path[i-1]][j]
        superstring += words[j][overlap_len:]

    return superstring


# Test
words = ["alex", "loves", "leetcode"]
print(shortest_superstring(words))

Java

import java.util.*;

public class ShortestSuperstringDP {
    private int calculateOverlap(String a, String b) {
        int maxOverlap = 0;
        int len1 = a.length(), len2 = b.length();
        for (int i = 1; i <= len1 && i <= len2; ++i) {
            if (a.endsWith(b.substring(0, i))) {
                maxOverlap = i;
            }
        }
        return maxOverlap;
    }

    private void reconstructPath(int last, int mask, int n, String[] words, List<Integer> path, int[][] parent) {
        while (mask != 0) {
            path.add(last);
            int temp = parent[mask][last];
            mask ^= (1 << last);
            last = temp;
        }
        Collections.reverse(path);
    }

    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) {
                overlap[i][j] = calculateOverlap(words[i], words[j]);
            }
        }

        int[][] dp = new int[1 << n][n];
        for (int[] row : dp)
            Arrays.fill(row, Integer.MAX_VALUE / 2);

        int[][] parent = new int[1 << n][n];
        for (int[] row : parent)
            Arrays.fill(row, -1);

        for (int i = 0; i < n; ++i) {
            dp[1 << i][i] = words[i].length();
        }

        for (int mask = 0; mask < (1 << n); ++mask) {
            for (int i = 0; i < n; ++i) {
                if ((mask & (1 << i)) != 0) {
                    for (int j = 0; j < n; ++j) {
                        if (i != j && (mask & (1 << j)) != 0) {
                            int prevMask = mask ^ (1 << i);
                            int currLength = dp[prevMask][j] + words[i].length() - overlap[j][i];
                            if (currLength < dp[mask][i]) {
                                dp[mask][i] = currLength;
                                parent[mask][i] = j;
                            }
                        }
                    }
                }
            }
        }

        int minLength = Integer.MAX_VALUE;
        int last = -1;
        for (int i = 0; i < n; ++i) {
            if (dp[(1 << n) - 1][i] < minLength) {
                minLength = dp[(1 << n) - 1][i];
                last = i;
            }
        }

        List<Integer> path = new ArrayList<>();
        reconstructPath(last, (1 << n) - 1, n, words, path, parent);

        StringBuilder result = new StringBuilder(words[path.get(0)]);
        for (int k = 1; k < path.size(); ++k) {
            int j = path.get(k), i = path.get(k - 1);
            result.append(words[j].substring(overlap[i][j]));
        }
        
        return result.toString();
    }

    public static void main(String[] args) {
        String[] words = {"alex", "loves", "leetcode"};
        ShortestSuperstringDP ssd = new ShortestSuperstringDP();
        System.out.println(ssd.shortestSuperstring(words));
    }
}

C++

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>

using namespace std;

vector<vector<int>> overlap;
vector<vector<int>> dp;
vector<vector<int>> parent;

int calculateOverlap(string &a, string &b) {
    int maxOverlap = 0;
    int len1 = a.length(), len2 = b.length();
    for (int i = 1; i <= len1 && i <= len2; ++i) {
        if (a.compare(len1 - i, i, b, 0, i) == 0) {
            maxOverlap = i;
        }
    }
    return maxOverlap;
}

void reconstructPath(int last, int mask, int n, vector<string> &words, string &result) {
    vector<int> path;
    while (mask) {
        path.push_back(last);
        int temp = parent[mask][last];
        mask ^= (1 << last);
        last = temp;
    }

    reverse(path.begin(), path.end());
    result = words[path[0]];
    for (int i = 1; i < path.size(); ++i) {
        int j = path[i], k = path[i - 1];
        result += words[j].substr(overlap[k][j]);
    }
}

string shortestSuperstring(vector<string> &words) {
    int n = words.size();
    overlap.assign(n, vector<int>(n, 0));

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i != j) {
                overlap[i][j] = calculateOverlap(words[i], words[j]);
            }
        }
    }

    dp.assign(1 << n, vector<int>(n, INT_MAX / 2));
    parent.assign(1 << n, vector<int>(n, -1));

    for (int i = 0; i < n; ++i) {
        dp[1 << i][i] = words[i].length();
    }

    for (int mask = 0; mask < (1 << n); ++mask) {
        for (int i = 0; i < n; ++i) {
            if (mask & (1 << i)) {
                for (int j = 0; j < n; ++j) {
                    if (mask & (1 << j) && i != j) {
                        int prev = mask ^ (1 << i);
                        int currCost = dp[prev][j] + words[i].length() - overlap[j][i];
                        if (currCost < dp[mask][i]) {
                            dp[mask][i] = currCost;
                            parent[mask][i] = j;
                        }
                    }
                }
            }
        }
    }

    int minLength = INT_MAX, last = 0;
    for (int i = 0; i < n; ++i) {
        if (dp[(1 << n) - 1][i] < minLength) {
            minLength = dp[(1 << n) - 1][i];
            last = i;
        }
    }

    string result;
    reconstructPath(last, (1 << n) - 1, n, words, result);
    return result;
}

int main() {
    vector<string> words = {"alex", "loves", "leetcode"};
    cout << shortestSuperstring(words) << endl;
    return 0;
}

JavaScript

function calculateOverlap(a, b) {
    let maxOverlap = 0;
    for (let i = 1; i <= Math.min(a.length, b.length); i++) {
        if (a.endsWith(b.substring(0, i))) {
            maxOverlap = i;
        }
    }
    return maxOverlap;
}

function shortestSuperstring(words) {
    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++) {
            overlap[i][j] = calculateOverlap(words[i], words[j]);
        }
    }

    const dp = Array.from({ length: 1 << n }, () => Array(n).fill(Infinity));
    const parent = Array.from({ length: 1 << n }, () => Array(n).fill(-1));

    for (let i = 0; i < n; i++) {
        dp[1 << i][i] = words[i].length;
    }

    for (let mask = 0; mask < (1 << n); mask++) {
        for (let i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                for (let j = 0; j < n; j++) {
                    if (i !== j && (mask & (1 << j))) {
                        const prevMask = mask ^ (1 << i);
                        const currLength = dp[prevMask][j] + words[i].length - overlap[j][i];
                        if (currLength < dp[mask][i]) {
                            dp[mask][i] = currLength;
                            parent[mask][i] = j;
                        }
                    }
                }
            }
        }
    }

    let minLength = Infinity;
    let last = -1;
    for (let i = 0; i < n; i++) {
        if (dp[(1 << n) - 1][i] < minLength) {
            minLength = dp[(1 << n) - 1][i];
            last = i;
        }
    }

    const path = [];
    let mask = (1 << n) - 1;
    while (mask) {
        path.push(last);
        const temp = parent[mask][last];
        mask ^= 1 << last;
        last = temp;
    }

    path.reverse();

    let superstring = words[path[0]];
    for (let i = 1; i < path.length; i++) {
        const j = path[i];
        const overlapLen = overlap[path[i - 1]][j];
        superstring += words[j].substring(overlapLen);
    }

    return superstring;
}

// Test
console.log(shortestSuperstring(['alex', 'loves', 'leetcode']));

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_WORDS 12
#define MAX_WORD_LENGTH 20
#define INF 999999

int overlap[MAX_WORDS][MAX_WORDS];
int dp[1 << MAX_WORDS][MAX_WORDS];
int parent[1 << MAX_WORDS][MAX_WORDS];

int calculateOverlap(char *a, char *b) {
    int maxOverlap = 0;
    int len1 = strlen(a), len2 = strlen(b);
    for (int i = 1; i <= len1 && i <= len2; ++i) {
        if (strncmp(a + len1 - i, b, i) == 0) {
            maxOverlap = i;
        }
    }
    return maxOverlap;
}

void constructPath(int last, int mask, int wordsSize, char words[MAX_WORDS][MAX_WORD_LENGTH + 1], char* res) {
    int index = 0;
    int bitmask = (1 << wordsSize) - 1;
    while (mask != 0) {
        int curr = last;
        int prev = parent[mask][curr];
        
        int overlapLen = (prev == -1) ? 0 : overlap[prev][curr];
        if (prev != -1) {
            strcat(res, words[curr] + overlapLen);
            index = strlen(res);
        } else {
            strcpy(res, words[curr]);
        }

        mask ^= (1 << curr);
        last = prev;
    }
    
    // Reverse the res array
    int len = strlen(res);
    for (int i = 0; i < len / 2; ++i) {
        char temp = res[i];
        res[i] = res[len - i - 1];
        res[len - i - 1] = temp;
    }
}

char *shortestSuperstring(char words[MAX_WORDS][MAX_WORD_LENGTH + 1], int wordsSize) {
    memset(dp, INF, sizeof(dp));
    for (int i = 0; i < wordsSize; ++i) {
        for (int j = 0; j < wordsSize; ++j) {
            if (i != j) {
                overlap[i][j] = calculateOverlap(words[i], words[j]);
            }
        }
    }

    for (int i = 0; i < wordsSize; ++i) {
        dp[1 << i][i] = (int)strlen(words[i]);
    }

    for (int mask = 0; mask < (1 << wordsSize); ++mask) {
        for (int i = 0; i < wordsSize; ++i) {
            if (mask & (1 << i)) {
                for (int j = 0; j < wordsSize; ++j) {
                    if (i != j && (mask & (1 << j))) {
                        int nextMask = mask ^ (1 << i);
                        int currCost = dp[nextMask][j] + (int)strlen(words[i]) - overlap[j][i];
                        if (currCost < dp[mask][i]) {
                            dp[mask][i] = currCost;
                            parent[mask][i] = j;
                        }
                    }
                }
            }
        }
    }

    int minLength = INF, last = -1;
    for (int i = 0; i < wordsSize; ++i) {
        if (dp[(1 << wordsSize) - 1][i] < minLength) {
            minLength = dp[(1 << wordsSize) - 1][i];
            last = i;
        }
    }

    char *res = malloc(255 * sizeof(char));
    memset(res, 0, 255);
    constructPath(last, (1 << wordsSize) - 1, wordsSize, words, res);

    return res;
}

int main() {
    char words[MAX_WORDS][MAX_WORD_LENGTH + 1] = {"alex", "loves", "leetcode"};
    int wordsSize = 3;
    
    char *result = shortestSuperstring(words, wordsSize);
    printf("%s\n", result);
    free(result);

    return 0;
}

using System;
using System.Collections.Generic;

class Program
{
    private static int CalculateOverlap(string a, string b)
    {
        int maxOverlap = 0;
        for (int i = 1; i <= Math.Min(a.Length, b.Length); i++)
        {
            if (a.Substring(a.Length - i) == b.Substring(0, i))
            {
                maxOverlap = i;
            }
        }
        return maxOverlap;
    }

    public static string ShortestSuperstring(string[] words)
    {
        int n = words.Length;
        int[][] overlap = new int[n][];
        for (int i = 0; i < n; i++)
        {
            overlap[i] = new int[n];
            for (int j = 0; j < n; j++)
            {
                overlap[i][j] = CalculateOverlap(words[i], words[j]);
            }
        }

        int[][] dp = new int[1 << n][];
        int[][] parent = new int[1 << n][];
        for (int i = 0; i < (1 << n); i++)
        {
            dp[i] = new int[n];
            parent[i] = new int[n];
            Array.Fill(dp[i], int.MaxValue / 2);
            Array.Fill(parent[i], -1);
        }
        for (int i = 0; i < n; i++)
        {
            dp[1 << i][i] = words[i].Length;
        }

        for (int mask = 0; mask < (1 << n); mask++)
        {
            for (int i = 0; i < n; i++)
            {
                if ((mask & (1 << i)) != 0)
                {
                    for (int j = 0; j < n; j++)
                    {
                        if (i != j && (mask & (1 << j)) != 0)
                        {
                            int prevMask = mask ^ (1 << i);
                            int currLength = dp[prevMask][j] + words[i].Length - overlap[j][i];
                            if (currLength < dp[mask][i])
                            {
                                dp[mask][i] = currLength;
                                parent[mask][i] = j;
                            }
                        }
                    }
                }
            }
        }

        int minLength = int.MaxValue;
        int last = -1;
        for (int i = 0; i < n; i++)
        {
            if (dp[(1 << n) - 1][i] < minLength)
            {
                minLength = dp[(1 << n) - 1][i];
                last = i;
            }
        }

        List<int> path = new List<int>();
        int mask = (1 << n) - 1;
        while (mask != 0)
        {
            path.Add(last);
            int temp = parent[mask][last];
            mask ^= 1 << last;
            last = temp;
        }

        path.Reverse();
        string superstring = words[path[0]];
        for (int i = 1; i < path.Count; i++)
        {
            int j = path[i];
            int overlapLen = overlap[path[i - 1]][j];
            superstring += words[j].Substring(overlapLen);
        }

        return superstring;
    }

    static void Main()
    {
        string[] words = { "alex", "loves", "leetcode" };
        Console.WriteLine(ShortestSuperstring(words));
    }
}

This Python solution uses dynamic programming and bitmasking to reduce complexity similar to solving TSP. The overlap matrix is precomputed, and dp array tracks minimum superstring lengths for subsets and specific last words, optimizing the shortest path with parent aiding path reconstruction.

Complexity

Time Complexity: O(n^2 * 2^n) given multiple states from masks.
Space Complexity: O(n * 2^n) for dp array storage.

Try this approach in the editor

Approach 5: Default Approach

func shortestSuperstring(words []string) string {
	n := len(words)
	g := make([][]int, n)
	for i, a := range words {
		g[i] = make([]int, n)
		for j, b := range words {
			if i != j {
				for k := min(len(a), len(b)); k > 0; k-- {
					if a[len(a)-k:] == b[:k] {
						g[i][j] = k
						break
					}
				}
			}
		}
	}
	dp := make([][]int, 1<<n)
	p := make([][]int, 1<<n)
	for i := 0; i < 1<<n; i++ {
		dp[i] = make([]int, n)
		p[i] = make([]int, n)
		for j := 0; j < n; j++ {
			p[i][j] = -1
			if ((i >> j) & 1) == 1 {
				pi := i ^ (1 << j)
				for k := 0; k < n; k++ {
					if ((pi >> k) & 1) == 1 {
						v := dp[pi][k] + g[k][j]
						if v > dp[i][j] {
							dp[i][j] = v
							p[i][j] = k
						}
					}
				}
			}
		}
	}
	j := 0
	for i := 0; i < n; i++ {
		if dp[(1<<n)-1][i] > dp[(1<<n)-1][j] {
			j = i
		}
	}
	arr := []int{j}
	vis := make([]bool, n)
	vis[j] = true
	for i := (1 << n) - 1; p[i][j] != -1; {
		k := i
		i ^= (1 << j)
		j = p[k][j]
		arr = append(arr, j)
		vis[j] = true
	}
	for i := 0; i < n; i++ {
		if !vis[i] {
			arr = append(arr, i)
		}
	}
	ans := &strings.Builder{}
	ans.WriteString(words[arr[n-1]])
	for i := n - 2; i >= 0; i-- {
		k := g[arr[i+1]][arr[i]]
		ans.WriteString(words[arr[i]][k:])
	}
	return ans.String()
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Approach 1: Using Dynamic Programming (DP) and Bitmasking	Time Complexity: O(n^2 * 2^n) where n is the number of words. This is because there are 2^n subsets and each subset operation can have O(n^2) complexity for managing overlaps. Space Complexity: O(n * 2^n) for storing DP and path arrays.
Approach 2: Traveling Salesman Problem (TSP) Heuristic	Time Complexity: O(n^2 * 2^n), where n is the number of strings. This is due to calculating overlaps for every pair and iterating over all subsets. Space Complexity: O(n * 2^n) for storing DP tables.
Approach 1: Permutation and Greedy Overlap	Time Complexity: O(n! * len^2) due to factorial permutations and overlap calculations. Space Complexity: O(n * len) for storing intermediate superstring results.
Approach 2: Dynamic Programming and TSP	Time Complexity: O(n^2 * 2^n) given multiple states from masks. Space Complexity: O(n * 2^n) for dp array storage.
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
Permutation + Greedy Overlap	O(n! · n · m)	O(n · m)	Understanding the core overlap idea or when n is extremely small
Dynamic Programming + Bitmask	O(n^2 · 2^n)	O(n · 2^n)	Optimal interview solution for n ≤ 12
TSP Graph DP	O(n^2 · 2^n)	O(n · 2^n)	When modeling the problem as a shortest Hamiltonian path
Greedy TSP Heuristic	O(n^2 · m)	O(n^2)	Fast approximation when exact optimal result is not required

Frequently asked questions

Is Find the Shortest Superstring easy or hard?

Find the Shortest Superstring is categorized as Hard. The challenge comes from recognizing that the problem reduces to a Traveling Salesman–style dynamic programming problem using bitmasks, combined with careful string overlap computation.

Find the Shortest Superstring Python/Java solution

Most implementations compute overlaps, run DP with bitmask states, and store parent pointers to reconstruct the order. Python, Java, and C++ solutions typically follow the same structure: overlap preprocessing, subset DP iteration, then building the final string using the optimal ordering.

How to solve Find the Shortest Superstring in O(n^2 · 2^n)?

First compute the overlap length between every pair of strings. Use a bitmask to represent which words are included and maintain dp[mask][i] for the best overlap when ending with word i. Transition by adding an unused word j and updating overlap using the precomputed matrix. After filling DP states, reconstruct the path that maximizes total overlap and build the final merged string.

What is the best approach for Find the Shortest Superstring?

Dynamic Programming with bitmasking is the most reliable approach. Precompute overlaps between every pair of words and run subset DP where dp[mask][i] tracks the best overlap ending with word i. The algorithm runs in O(n^2 · 2^n) time and reconstructs the optimal ordering that produces the shortest superstring.

Is Find the Shortest Superstring asked at Google/Amazon/Meta?

Shortest superstring style problems appear in interviews at companies like Google, Amazon, and Meta because they combine graph modeling with dynamic programming. The problem tests your ability to transform a string problem into a Traveling Salesman–style DP using bitmasks.

What data structure is used in Find the Shortest Superstring?

The solution uses arrays or matrices to store pairwise overlaps, plus a DP table indexed by bitmask and last node. Bitmasks efficiently represent subsets of words, enabling transitions similar to Hamiltonian path or TSP dynamic programming.

What is the time complexity of Find the Shortest Superstring?

The optimal DP + bitmask solution runs in O(n^2 · 2^n) time and O(n · 2^n) space, where n is the number of strings. Pairwise overlap preprocessing adds O(n^2 · m) where m is the average string length. Brute-force permutation solutions take O(n! · n · m) and are only feasible for very small inputs.

Find the Shortest Superstring solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Using Dynamic Programming (DP) and Bitmasking

Approach 2: Approach 2: Traveling Salesman Problem (TSP) Heuristic

Approach 3: Approach 1: Permutation and Greedy Overlap

Approach 4: Approach 2: Dynamic Programming and TSP

Approach 5: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Find the Shortest Superstring solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Using Dynamic Programming (DP) and Bitmasking

Approach 2: Approach 2: Traveling Salesman Problem (TSP) Heuristic

Approach 3: Approach 1: Permutation and Greedy Overlap

Approach 4: Approach 2: Dynamic Programming and TSP

Approach 5: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems