LeetCode Solutions Blog

Shortest String That Contains Three Strings

Number: 2877

Difficulty: Medium

Paid? No

Problem Description

Given three strings a, b, and c, find the shortest possible string that contains all three as substrings. If multiple such strings exist, return the lexicographically smallest one.

Key Insights

Only three strings are involved, so we can try all permutations (only 6) to find the optimal ordering.
Before merging, remove any string that is already a substring of another to potentially reduce work.
Merging two strings greedily by maximizing the overlap between the suffix of the first and the prefix of the second can yield the shortest superstring for that pair.
When two merged results have the same length, lexicographic comparison is used to choose the answer.

Space and Time Complexity

Time Complexity: O(1) in the context of permutation and merge checks since there are just 3 strings and each merge is O(n^2) with n at most 100. Space Complexity: O(n) where n is the maximum length of the strings (for storing merged results).

Solution

We first check if any of the three strings is contained in another; if yes, we can discard the contained string as it is redundant. Then, for each permutation of the remaining strings, we merge them in order using a helper merge function. This merge function checks if the second string is already a substring of the first (and returns the first in that case), or otherwise finds the maximum overlap of the suffix of the first with the prefix of the second and combines them accordingly. Finally, we update our best candidate based on the minimum length, and if lengths are equal, the lexicographically smallest string is chosen.

Code Solutions

# Merge helper: combines s1 and s2 with maximum overlap
def merge_strings(s1, s2):
    # If s2 is already in s1, just return s1.
    if s2 in s1:
        return s1
    max_overlap = 0
    # Find maximum overlap where suffix of s1 equals prefix of s2.
    for i in range(1, min(len(s1), len(s2)) + 1):
        if s1[-i:] == s2[:i]:
            max_overlap = i
    # Merge s1 and s2, adding the non-overlapping part of s2.
    return s1 + s2[max_overlap:]

# Main function to find the shortest superstring
def shortestSuperstring(a, b, c):
    from itertools import permutations
    # Remove redundant strings that are substrings of others.
    strings = [a, b, c]
    unique_strings = []
    for s in strings:
        if not any(s != other and s in other for other in strings):
            unique_strings.append(s)
    # If duplicate removals cause list to be empty, set unique_strings to strings.
    if not unique_strings: 
        unique_strings = strings

    best = None
    # Try all orders of the remaining strings.
    for order in permutations(unique_strings):
        merged = order[0]
        for i in range(1, len(order)):
            merged = merge_strings(merged, order[i])
        # Update candidate if best is None or if a shorter superstring is found,
        # or if equal length, the lexicographically smaller one.
        if best is None or len(merged) < len(best) or (len(merged) == len(best) and merged < best):
            best = merged
    return best

# Example usage:
a = "abc"
b = "bca"
c = "aaa"
print(shortestSuperstring(a, b, c))  # Expected output: "aaabca"