#943

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Find the Shortest Superstring

This problem requires constructing the shortest string containing all input words using state transition dynamic programming and bitmasking.

array string dynamic programming bit manipulation bitmask

Problem Statement

Given an array of unique strings, your task is to return the shortest string that contains each word as a substring. If multiple strings have the same minimal length, any valid one is acceptable. No word in the array is a substring of another.

For example, given words = ["alex","loves","leetcode"], one shortest superstring is "alexlovesleetcode". The problem requires considering all permutations and overlaps, emphasizing efficient state transition dynamic programming rather than brute force concatenation.

Examples

Example 1

Input: words = ["alex","loves","leetcode"]

Output: "alexlovesleetcode"

All permutations of "alex","loves","leetcode" would also be accepted.

Example 2

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

Output: "gctaagttcatgcatc"

Example details omitted.

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 Approach

Compute Pairwise Overlaps

Create a matrix storing the maximum overlap length between each pair of words. This allows the DP step to quickly know how much each word can extend another, reducing redundant computation and directly tying into the state transition dynamic programming pattern.

Dynamic Programming with Bitmask

Use a DP table where dp[mask][i] represents the shortest superstring ending with word i using words indicated by mask. Transition by adding a word j not in mask and update dp[mask | (1<<j)][j] using previously computed overlaps. This method handles all subsets efficiently while controlling exponential growth.

Reconstruct Shortest Superstring

After filling the DP table, backtrack from the state with all words used to reconstruct the order of words that yields the shortest superstring. Concatenate the words respecting the precomputed overlaps to produce the final minimal-length result.

Complexity Analysis

Metric	Value
Time	O(N^2 (2^N + W))
Space	O(N (2^N + W))

Time complexity is O(N^2 * 2^N + N^2 * W) due to computing overlaps and DP transitions, where N is the number of words and W is the average word length. Space complexity is O(N * 2^N + N^2) to store DP states and overlaps.

What Interviewers Usually Probe

Expect discussion of bitmask DP and its exponential subset growth pattern.
Look for correct calculation of word overlaps and handling edge cases in reconstruction.
Watch for clarity in state transition definition and why each DP entry correctly represents a partial solution.

Common Pitfalls or Variants

Common pitfalls

Ignoring the fact that overlaps are directional and dp[i][mask] must track the ending word.
Attempting brute-force permutation generation which is infeasible for N > 10.
Forgetting to reconstruct the string correctly after DP, leading to invalid superstrings.

Follow-up variants

Minimize superstring for a subset of words where some words may repeat.
Find a superstring using weighted overlaps for prioritizing certain word concatenations.
Compute the shortest superstring but allow some words to be omitted based on constraints.

FAQ

What is the main pattern used in Find the Shortest Superstring?

The problem is solved using state transition dynamic programming with bitmasking to track subsets of words efficiently.

Can the words in the input array be substrings of each other?

No, the problem guarantees that no word is a substring of another, simplifying overlap calculations.

Why is a brute-force permutation approach impractical?

Because the number of permutations grows factorially with the number of words, leading to infeasible computation for N > 10.

How are overlaps computed between two words?

For each pair, calculate the longest suffix of the first matching a prefix of the second, which determines the maximal overlap length.

Does GhostInterview provide step-by-step reconstruction guidance?

Yes, it walks through the backtracking of the DP table to assemble the shortest superstring correctly.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

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)

Continue Practicing

#691 stickers to spell word #1255 maximum score words formed by letters #996 number of squareful arrays