Shortest String That Contains Three Strings - Solution & Explanation

Problem Overview: You are given three strings a, b, and c. Build the shortest possible string that contains all three as substrings. If multiple answers have the same length, return the lexicographically smallest one.

The core challenge is minimizing redundant characters when combining the strings. If the suffix of one string overlaps with the prefix of another, you should merge them instead of concatenating blindly.

Approach 1: Greedy Overlap with Permutation Enumeration (O(n^2) time, O(n) space)

This approach tries every ordering of the three strings (there are only 3! = 6 permutations). For each order, merge strings one by one using maximum overlap. To merge two strings x and y, first check if y already exists inside x. If not, iterate from the largest possible overlap length down to 0 and match the suffix of x with the prefix of y. Append only the non-overlapping part.

Because each overlap check may scan up to the string length, merging costs O(n^2) in the worst case. After generating a merged string for each permutation, choose the shortest result and break ties using lexicographical comparison. The small constant (only six permutations) keeps the solution efficient in practice. This method relies heavily on careful string manipulation and simple greedy decisions about overlaps.

Approach 2: Dynamic Programming with Memoization (O(n^2 * k!) time, O(n * k) space)

A more structured solution models the problem as merging strings while tracking which ones have already been used. Use a bitmask to represent the chosen strings and memoize the best merged result for each state. For each transition, attempt to append a remaining string using the same maximum-overlap merge routine.

The memoization avoids recomputing the best merged result for identical states. While the search space is small for three strings, this approach demonstrates how the idea generalizes to more strings. It combines dynamic programming with substring overlap computation.

Recommended for interviews: The greedy permutation solution is what most interviewers expect. Enumerating all six orders shows you recognize the small input size, and the overlap merge demonstrates practical string manipulation. Mentioning the DP formulation shows deeper understanding, but implementing the greedy overlap method quickly and correctly is usually enough to pass the interview.