Find the Shortest Superstring

Find the Shortest Superstring

1. What is this problem about?

The Find the Shortest Superstring interview question is a difficult string optimization task. You are given an array of strings, and you need to find the shortest string that contains every string in the array as a substring. You can overlap strings if the suffix of one matches the prefix of another (e.g., "abcd" and "cdef" can become "abcdef").

2. Why is this asked in interviews?

Companies like Google and DE Shaw ask the Find the Shortest Superstring coding problem to evaluate a candidate's mastery of Dynamic Programming with Bitmasking. This is essentially a variation of the Traveling Salesperson Problem (TSP), where the "cities" are strings and the "distance" is the additional length added when merging them. It tests your ability to handle exponential complexity elegantly.

3. Algorithmic pattern used

This problem relies on Bitmask DP and Pre-processing.

1. Pre-calculate Overlaps: Create a 2D array overlap[i][j] that stores the maximum overlap between the suffix of words[i] and the prefix of words[j].
2. DP State: dp[mask][i] represents the length of the shortest superstring formed by using the set of words in mask, ending with words[i].
3. Transitions: dp[mask | (1 << j)][j] = min(dp[mask][i] + length(words[j]) - overlap[i][j]).
4. Reconstruction: After finding the minimum total length, backtrack through the DP table to reconstruct the actual string.

4. Example explanation

Words: ["alex", "loves", "leetcode"]

• "alex" + "loves" -> Overlap "l" or "le"? No, no significant overlap.
• "abcde", "cdefg" -> Overlap "cde" (length 3). Shortest superstring: "abcdefg" (length 7 instead of 10). The DP explores all $N!$ orders of strings using the bitmask to keep it at $O(2^N \cdot N^2)$.

5. Common mistakes candidates make

• Greedy Approach: Trying to merge the two strings with the largest overlap first. While fast, this doesn't guarantee the global shortest superstring.
• State Reconstruction: Finding the length correctly but failing to correctly rebuild the string from the DP table.
• Overlap logic: Calculating the overlap incorrectly (e.g., matching middle parts instead of strictly prefix/suffix).

6. Interview preparation tip

Master Bitmask DP. It is the standard solution for any problem that involves finding an optimal order of a small number of items ($N \leq 15-20$). If you can explain the TSP analogy, you show strong algorithmic maturity.