Scale Engineer

Find the Shortest Superstring

Hard
#0897Time: 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.1 company
Patterns
Dynamic ProgrammingBit ManipulationBitmask
Data structures
ArrayString
Companies
DE Shaw

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

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;    }}

Complexity

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.

Trade-offs

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.

Solutions

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();  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem