Given an array of strings words, return the smallest string that contains each string inwordsas 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.
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).
⏰ 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)#
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.
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.
classSolution {
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;
}
};
classSolution {
public String shortestSuperstring(String[] words) {
int n = words.length;
int[][] overlap =newint[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 =newint[1<<n][n];
int[][] parent =newint[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 =newboolean[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();
}
}
classSolution {
funshortestSuperstring(words: Array<String>): String {
val n = words.size
val overlap = Array(n) { IntArray(n) }
for (i in0 until n)
for (j in0 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 in1 until (1 shl n)) {
for (j in0 until n) {
if (mask and (1 shl j) ==0) continueval pmask = mask xor (1 shl j)
if (pmask ==0) continuefor (i in0 until n) {
if (pmask and (1 shl i) ==0) continueval 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) - 1var last = 0var best = -1for (i in0 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]] = truefor (k in1 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 in0 until n) if (!seen[i]) ans.append(words[i])
return ans.toString()
}
}
classSolution:
defshortestSuperstring(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: continuefor 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):
ifnot (mask & (1<<j)): continue pmask = mask ^ (1<<j)
if pmask ==0: continuefor i in range(n):
ifnot (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, -1for 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]] =Truefor k in range(1, len(path)):
i, j = path[k-1], path[k]
ans += words[j][overlap[i][j]:]
seen[j] =Truefor i in range(n):
ifnot seen[i]: ans += words[i]
return ans
impl Solution {
pubfnshortest_superstring(words: Vec<String>) -> String {
let n = words.len();
letmut overlap =vec![vec![0; n]; n];
for i in0..n {
for j in0..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;
}
}
}
}
letmut dp =vec![vec![0; n]; 1<<n];
letmut parent =vec![vec![-1; n]; 1<<n];
for mask in1..1<<n {
for j in0..n {
if mask & (1<<j) ==0 { continue; }
let pmask = mask ^ (1<<j);
if pmask ==0 { continue; }
for i in0..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 asi32;
}
}
}
}
let (mut mask, mut last, mut best) = ((1<<n)-1, 0, -1);
for i in0..n {
if dp[mask][i] > best { best = dp[mask][i]; last = i; }
}
letmut path =vec![];
while last !=-1 {
path.push(last);
let tmp = parent[mask][last];
mask ^=1<< last;
last =if tmp ==-1 { -1 } else { tmp asusize };
}
path.reverse();
letmut seen =vec![false; n];
letmut ans = words[path[0]].clone();
seen[path[0]] =true;
for k in1..path.len() {
let i = path[k-1]; let j = path[k];
ans +=&words[j][overlap[i][j]..];
seen[j] =true;
}
for i in0..n { if!seen[i] { ans +=&words[i]; } }
ans
}
}