# Find the Shortest Superstring
**Difficulty:** HARD
[External](https://leetcode.com/problems/find-the-shortest-superstring)
Canonical: https://scaleengineer.com/dsa/problems/find-the-shortest-superstring
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Bitmask](https://scaleengineer.com/dsa/patterns/bitmask)
**Data structures:** Array, String
**Companies:** [DE Shaw](https://scaleengineer.com/companies/de-shaw)
---
## 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**.

# Approaches
## Brute-force with Permutations
This approach exhaustively explores every possible ordering of the input strings. For each ordering, which is a permutation of the `words` array, it constructs the corresponding superstring by merging adjacent strings with the maximum possible overlap. It maintains a record of the shortest superstring found throughout this process and returns it as the final answer. While conceptually straightforward, its factorial time complexity makes it impractical for the constraints of this problem.
**Time:** O(n! * n * L^2), where `n` is the number of words and `L` is the maximum length. There are `n!` permutations. For each, we iterate through `n-1` pairs of words to build the superstring. Merging involves calculating overlap, which takes O(L^2), and string concatenation. · **Space:** O(n * L), where `n` is the number of words and `L` is the maximum length of a word. This space is used for the recursion stack and to store the generated superstrings.
**Pros:** Simple to understand and implement.; Guaranteed to find the optimal solution by checking every possibility.
**Cons:** Extremely high time complexity, making it infeasible for `n` larger than about 8-10.; Redundant computations, as overlaps between pairs of strings are calculated multiple times across different permutations.
### Explanation
The core idea is to try every single arrangement of the words and see which one produces the shortest combined string. We can implement this using a recursive function that generates all permutations of the `words` array.

For each permutation, we build the superstring from left to right. We start with the first word in the permutation. Then, we take the second word, find how much its beginning overlaps with the end of our current superstring, and append the rest of the second word. We repeat this process until all words in the permutation have been added.

After constructing a superstring for a permutation, we compare its length with the shortest one we've found so far. If the new one is shorter, we update our answer. After checking all `n!` permutations, we will have found the optimal solution.

For example, if `words = ["a", "b", "c"]`, we would test permutations like `("a", "b", "c")` -> `"abc"`, `("a", "c", "b")` -> `"acb"`, etc., and find the shortest result.

```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

class Solution {
    private String shortestSuperstring = "";

    public String shortestSuperstring(String[] words) {
        int n = words.length;
        if (n == 0) return "";
        if (n == 1) return words[0];

        List<String> wordList = new ArrayList<>(Arrays.asList(words));
        permute(wordList, 0);
        return shortestSuperstring;
    }

    private void permute(List<String> words, int start) {
        if (start == words.size()) {
            StringBuilder currentSuperstring = new StringBuilder(words.get(0));
            for (int i = 1; i < words.size(); i++) {
                String prev = words.get(i - 1);
                String curr = words.get(i);
                int overlap = calculateOverlap(prev, curr);
                currentSuperstring.append(curr.substring(overlap));
            }
            if (shortestSuperstring.isEmpty() || currentSuperstring.length() < shortestSuperstring.length()) {
                shortestSuperstring = currentSuperstring.toString();
            }
            return;
        }

        for (int i = start; i < words.size(); i++) {
            Collections.swap(words, start, i);
            permute(words, start + 1);
            Collections.swap(words, start, i); // backtrack
        }
    }

    private int calculateOverlap(String s1, String s2) {
        int maxOverlap = 0;
        for (int k = Math.min(s1.length(), s2.length()); k > 0; k--) {
            if (s1.endsWith(s2.substring(0, k))) {
                maxOverlap = k;
                break;
            }
        }
        return maxOverlap;
    }
}
```
### Algorithm
- Define a recursive function, say `permute(wordList, start)`, that generates all permutations of the input `words`.
- The base case for the recursion is when `start` reaches the end of the list. At this point, a full permutation has been generated.
- For each complete permutation, construct the corresponding superstring. Start with the first word, then for each subsequent word, find the maximum overlap with the previous word and append the non-overlapping part.
- Keep track of the shortest superstring found so far across all permutations.
- The main function initializes the process by calling the recursive function with `start = 0`.
- A helper function `calculateOverlap(s1, s2)` is used to find the length of the longest suffix of `s1` that is also a prefix of `s2`.

## Dynamic Programming with Bitmask (TSP)
This problem can be framed as the Traveling Salesperson Problem (TSP), an NP-hard problem. Each string represents a 'city', and the 'distance' or cost of traveling from city `i` to city `j` is the length added when appending `words[j]` after `words[i]`, which is `words[j].length() - overlap(words[i], words[j])`. The goal is to find a path that visits all cities exactly once with minimum total cost. For the given constraint of `n <= 12`, this TSP variant can be solved optimally using dynamic programming with bitmasking.
**Time:** O(n^2 * L^2 + 2^n * n^2), where `n` is the number of words and `L` is their max length. `O(n^2 * L^2)` is for pre-calculating all pairwise overlaps. `O(2^n * n^2)` is for filling the DP table. · **Space:** O(2^n * n), where `n` is the number of words. This space is dominated by the `dp` and `parent` tables.
**Pros:** Guaranteed to find the optimal solution.; Significantly more efficient than brute-force for the given constraints.; It's a standard and powerful technique for solving TSP-like problems on small datasets.
**Cons:** The exponential time and space complexity with respect to `n` makes it infeasible for large `n` (e.g., `n > 20`).; The implementation is significantly more complex than the brute-force approach.
### Explanation
This approach provides an efficient way to solve the problem by avoiding the redundant computations of the brute-force method. It uses dynamic programming to build the solution from smaller subproblems to larger ones.

1.  **Pre-computation of Overlaps:** We first create an `n x n` matrix to store the length of the maximum overlap for every pair of words `(words[i], words[j])`. This prevents recalculating these values repeatedly.

2.  **DP State:** The state of our DP is `dp[mask][i]`, representing the length of the shortest superstring that includes the set of words indicated by the bitmask `mask`, and ends with the word `words[i]`.

3.  **DP Transitions:** We build up the `dp` table by increasing the size of the subset of words. To compute `dp[mask][i]`, we look at all possible previous words `words[j]` that could have come before `words[i]`. The previous state would be for the subset `mask` without `words[i]`, ending in `words[j]`. We transition from `dp[prev_mask][j]` to `dp[mask][i]` by adding the cost of appending `words[i]` after `words[j]`. We take the minimum over all possible `j`.

4.  **Path Reconstruction:** Simply knowing the minimum length is not enough; we need the actual string. We use an auxiliary `parent[mask][i]` table to store which previous word `j` gave the optimal solution for `dp[mask][i]`. After the DP table is filled, we find the end of the optimal path (the `i` that minimizes `dp[(1<<n)-1][i]`) and backtrack using the `parent` table to reconstruct the sequence of words.

5.  **Final Construction:** With the optimal sequence of words, we can easily construct the shortest superstring by joining them, taking care to use the overlaps.

```java
import java.util.Arrays;

class Solution {
    public String shortestSuperstring(String[] words) {
        int n = words.length;
        if (n == 0) return "";
        if (n == 1) return words[0];

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

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

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

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

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

        int[] path = new int[n];
        int currentMask = finalMask;
        for (int i = n - 1; i >= 0; i--) {
            path[i] = lastIndex;
            int prevIndex = parent[currentMask][lastIndex];
            currentMask ^= (1 << lastIndex);
            lastIndex = prevIndex;
        }

        StringBuilder result = new StringBuilder(words[path[0]]);
        for (int i = 1; i < n; i++) {
            int prev = path[i - 1];
            int curr = path[i];
            result.append(words[curr].substring(overlaps[prev][curr]));
        }

        return result.toString();
    }

    private int calculateOverlap(String s1, String s2) {
        int maxOverlap = 0;
        for (int k = Math.min(s1.length(), s2.length()); k > 0; k--) {
            if (s1.endsWith(s2.substring(0, k))) {
                maxOverlap = k;
                break;
            }
        }
        return maxOverlap;
    }
}
```
### Algorithm
- **Step 1: Pre-computation.** Calculate and store the overlap length for every ordered pair of strings `(words[i], words[j])` in a 2D array, `overlaps[i][j]`.
- **Step 2: DP State.** Define a 2D DP table, `dp[mask][i]`, to store the length of the shortest superstring for the subset of words represented by `mask`, ending with `words[i]`. Also, define a `parent[mask][i]` table to reconstruct the path.
- **Step 3: Base Case.** Initialize the DP table for subsets of size one: `dp[1 << i][i] = words[i].length()` for all `i` from 0 to `n-1`.
- **Step 4: DP Transition.** Iterate through masks from 1 to `(1 << n) - 1`. For each `mask`, and for each word `i` in the subset `mask`, find the minimum path length by trying every other word `j` in the subset as the previous word. The transition is: `dp[mask][i] = min(dp[mask ^ (1 << i)][j] + words[i].length() - overlaps[j][i])`.
- **Step 5: Find Final Result.** After filling the table, find the minimum value in `dp[(1 << n) - 1][i]` for all `i`. This gives the length of the shortest superstring and the index of its last word.
- **Step 6: Reconstruct Path.** Backtrack using the `parent` table from the final state to find the optimal permutation of words.
- **Step 7: Build Superstring.** Construct the final superstring using the optimal permutation and the pre-calculated overlaps.

# Solutions
### Java

```java
class Solution {
public
  String shortestSuperstring(String[] words) {
    int n = words.length;
    int[][] g = new int[n][n];
    for (int i = 0; i < n; ++i) {
      String a = words[i];
      for (int j = 0; j < n; ++j) {
        String b = words[j];
        if (i != j) {
          for (int k = Math.min(a.length(), b.length()); k > 0; --k) {
            if (a.substring(a.length() - k).equals(b.substring(0, k))) {
              g[i][j] = k;
              break;
            }
          }
        }
      }
    }
    int[][] dp = new int[1 << n][n];
    int[][] p = new int[1 << n][n];
    for (int i = 0; i < 1 << n; ++i) {
      Arrays.fill(p[i], -1);
      for (int j = 0; j < n; ++j) {
        if (((i >> j) & 1) == 1) {
          int pi = i ^ (1 << j);
          for (int k = 0; k < n; ++k) {
            if (((pi >> k) & 1) == 1) {
              int v = dp[pi][k] + g[k][j];
              if (v > dp[i][j]) {
                dp[i][j] = v;
                p[i][j] = k;
              }
            }
          }
        }
      }
    }
    int j = 0;
    for (int i = 0; i < n; ++i) {
      if (dp[(1 << n) - 1][i] > dp[(1 << n) - 1][j]) {
        j = i;
      }
    }
    List<Integer> arr = new ArrayList<>();
    arr.add(j);
    for (int i = (1 << n) - 1; p[i][j] != -1;) {
      int k = i;
      i ^= (1 << j);
      j = p[k][j];
      arr.add(j);
    }
    Set<Integer> vis = new HashSet<>(arr);
    for (int i = 0; i < n; ++i) {
      if (!vis.contains(i)) {
        arr.add(i);
      }
    }
    Collections.reverse(arr);
    StringBuilder ans = new StringBuilder(words[arr.get(0)]);
    for (int i = 1; i < n; ++i) {
      int k = g[arr.get(i - 1)][arr.get(i)];
      ans.append(words[arr.get(i)].substring(k));
    }
    return ans.toString();
  }
}

```

### CPP

```cpp
class Solution {
public:
  string shortestSuperstring(vector<string> &words) {
    int n = words.size();
    vector<vector<int>> g(n, vector<int>(n));
    for (int i = 0; i < n; ++i) {
      auto a = words[i];
      for (int j = 0; j < n; ++j) {
        auto b = words[j];
        if (i != j) {
          for (int k = min(a.size(), b.size()); k > 0; --k) {
            if (a.substr(a.size() - k) == b.substr(0, k)) {
              g[i][j] = k;
              break;
            }
          }
        }
      }
    }
    vector<vector<int>> dp(1 << n, vector<int>(n));
    vector<vector<int>> p(1 << n, vector<int>(n, -1));
    for (int i = 0; i < 1 << n; ++i) {
      for (int j = 0; j < n; ++j) {
        if ((i >> j) & 1) {
          int pi = i ^ (1 << j);
          for (int k = 0; k < n; ++k) {
            if ((pi >> k) & 1) {
              int v = dp[pi][k] + g[k][j];
              if (v > dp[i][j]) {
                dp[i][j] = v;
                p[i][j] = k;
              }
            }
          }
        }
      }
    }
    int j = 0;
    for (int i = 0; i < n; ++i) {
      if (dp[(1 << n) - 1][i] > dp[(1 << n) - 1][j]) {
        j = i;
      }
    }
    vector<int> arr = {j};
    for (int i = (1 << n) - 1; p[i][j] != -1;) {
      int k = i;
      i ^= (1 << j);
      j = p[k][j];
      arr.push_back(j);
    }
    unordered_set<int> vis(arr.begin(), arr.end());
    for (int i = 0; i < n; ++i) {
      if (!vis.count(i)) {
        arr.push_back(i);
      }
    }
    reverse(arr.begin(), arr.end());
    string ans = words[arr[0]];
    for (int i = 1; i < n; ++i) {
      int k = g[arr[i - 1]][arr[i]];
      ans += words[arr[i]].substr(k);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def shortestSuperstring(self, words: List[str]) -> str: n = len(words) g = [[0] * n for _ in range(n)] for i, a in enumerate(words): for j, b in enumerate(words): if i != j: for k in range(min(len(a), len(b)), 0, - 1): if a[- k:] == b[: k]: g[i][j] = k break dp = [[0] * n for _ in range(1 << n)] p = [[- 1] * n for _ in range(1 << n)] for i in range(1 << n): for j in range(n): if (i >> j) & 1: pi = i ^ (1 << j) for k in range(n): if (pi >> k) & 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 in range(n): if dp[- 1][i] > dp[- 1][j]: j = i arr = [j] i = (1 << n) - 1 while p[i][j] != - 1: i, j = i ^ (1 << j), p[i][j] arr . append(j) arr = arr[:: - 1] vis = set(arr) arr . extend([j for j in range(n) if j not in vis]) ans = [words[arr[0]]] + [words[j][g[i][j]:] for i, j in pairwise(arr)] return '' . join(ans)

```