Shortest String That Contains Three Strings

Problem Description

Given three strings a, b, and c, your task is to find a string that has the minimum length and contains all three strings as substrings. If there are multiple such strings, return the lexicographically smallest one.

Key Insights

• The problem involves finding the shortest common superstring that includes all three given strings as substrings.
• Overlapping substrings can be utilized to minimize the length of the resulting string.
• A brute force approach would involve generating all permutations of the input strings and checking for overlaps.
• Lexicographical ordering is important when multiple valid solutions exist.

Space and Time Complexity

Time Complexity: O(n!) for generating permutations of strings, plus O(n^2) for checking overlaps, where n is the number of strings (in this case, 3). Overall, the complexity is manageable due to the small fixed number of strings. Space Complexity: O(n) for storing the resulting string and overlaps.

Solution

The solution uses a brute force approach by generating all possible permutations of the input strings. For each permutation, we calculate the minimum length string that contains all three strings by maximizing overlaps. The algorithm will:

1. Generate all permutations of the strings.
2. For each permutation, compute the combined string by merging with maximum overlap.
3. Track the shortest result and in case of ties, choose the lexicographically smallest string.

Code Solutions