Shortest String That Contains Three Strings

Shortest String That Contains Three Strings

What is this problem about?

The Shortest String That Contains Three Strings interview question gives you three strings a, b, and c. Find the shortest string that contains all three as substrings. If there are multiple shortest strings, return the lexicographically smallest one. This is a string merging problem requiring overlap computation between all orderings of the three strings.

Why is this asked in interviews?

DE Shaw, Google, and Bloomberg ask this problem because it's the 3-string variant of the shortest superstring problem — a classic but NP-hard problem that becomes tractable for only 3 strings. You try all 6 permutations of (a, b, c), compute the shortest merged string for each ordering, and take the minimum. It tests string overlap computation, permutation enumeration, and subset relationship detection.

Algorithmic pattern used

The pattern is permutation enumeration with overlap merging. Two helper functions: (1) contains(s, t) — check if t is a substring of s. (2) merge(s, t) — if t is a suffix/prefix overlap with s, return s + t[overlap_length:]; else return s + t. For all 6 permutations of (a,b,c), merge them left to right after removing any strings that are substrings of others. Among all 6 merged results, return the shortest; break ties with lexicographic comparison.

Example explanation

a = "ab", b = "bcd", c = "cdx".

Permutation (a, b, c): merge "ab"+"bcd" → "abcd" (overlap 'b'), then "abcd"+"cdx" → "abcdx" (overlap 'cd'). Length 5. Permutation (a, c, b): merge "ab"+"cdx" → "abcdx" (no overlap), then + "bcd" → "abcdx" already contains "bcd"? No. "abcdxbcd" length 8.

Check if b="bcd" is contained in "abcdx" → "bcd" is a substring of "abcdx" ✓. So "abcdx" suffices!

Result: "abcdx" (length 5).

Common mistakes candidates make

• Not checking if one string is a substring of another before merging — if b is already in a, don't add it separately.
• Computing only the merge of adjacent pairs without trying all 6 permutations — the optimal ordering is not always alphabetical.
• Incorrectly computing the overlap length — find the longest suffix of s that matches a prefix of t, not just any overlap.
• Not breaking lexicographic ties — when lengths are equal, return the lexicographically smaller result.

Interview preparation tip

For the Shortest String That Contains Three Strings coding problem, the string greedy enumeration interview pattern is the approach. With only 3 strings, exhaustively trying all 6 permutations is acceptable. Google and Bloomberg interviewers may ask "what if there were 10 strings?" — the general problem is NP-hard; for 10 strings, bitmask DP with 2^10 = 1024 states and 10 transitions gives an O(2^n × n^2) solution. Practice computing the overlap between two strings using two-pointer or find() — the overlap computation is the heart of this problem.