Problem Description

You are given three strings a, b, and c. Your task is to find the shortest possible string that contains all three strings as substrings.

A substring is a contiguous sequence of characters within a string. For example, "abc" is a substring of "xabcy" but not of "xabyc".

The goal is to create a string that:

1. Contains string a as a substring
2. Contains string b as a substring
3. Contains string c as a substring
4. Has the minimum possible length

If there are multiple strings with the same minimum length that satisfy these conditions, return the lexicographically smallest one.

Lexicographical ordering means dictionary order - a string is lexicographically smaller than another string of the same length if at the first position where they differ, it has a character that comes earlier in the alphabet.

For example:

• If a = "abc", b = "bca", and c = "aaa", one possible answer could be "aaabca" which contains all three strings as substrings:
  • "aaa" is present starting at index 0
  • "abc" is present starting at index 2
  • "bca" is present starting at index 3

The solution involves trying different ways to merge the strings by finding overlaps between them and choosing the arrangement that produces the shortest result, with ties broken by lexicographical order.

Intuition

The key insight is that when we want to combine multiple strings into one while minimizing the total length, we should look for overlapping parts between strings. For instance, if we have "abc" and "bcd", instead of concatenating them as "abcbcd" (length 7), we can overlap them as "abcd" (length 4) since "bc" is common.

When dealing with three strings, the order in which we merge them matters. Consider merging "abc", "bca", and "cab". If we merge "abc" with "bca" first, we get "abca". Then merging with "cab" gives us "abcab". But if we started with "bca" and "cab", we'd get "bcab", and then merging with "abc" gives us "abcab" or potentially something different depending on overlaps.

Since there are only 3 strings, we can try all possible orderings - there are exactly 3! = 6 permutations. For each permutation, we merge the strings in that order and keep track of the shortest result.

The merging strategy for two strings works as follows:

1. First check if one string is already contained in the other - if so, just return the longer string
2. Otherwise, find the maximum overlap: check if the end of the first string matches the beginning of the second string
3. Start with the largest possible overlap and work down to find a match
4. If no overlap exists, simply concatenate the strings

By trying all 6 possible orderings and applying this merging strategy, we're guaranteed to find the optimal solution. Among all solutions with minimum length, we pick the lexicographically smallest one.

Learn more about Greedy patterns.

Solution Approach

The solution uses a helper function f(s, t) to merge two strings optimally, and then applies this function across all permutations of the three input strings.

Helper Function f(s, t) - Merging Two Strings:

1. Check containment: If string s is already contained in t, return t. If t is contained in s, return s. This handles cases where one string is a substring of another.

2. Find maximum overlap: If neither contains the other, look for the longest overlap between the end of s and the beginning of t:

   • Start with the minimum of the two string lengths (since overlap can't exceed the shorter string)
   • Check progressively smaller overlaps from min(m, n) down to 1
   • For each overlap length i, check if the last i characters of s match the first i characters of t: s[-i:] == t[:i]
   • If a match is found, return s + t[i:] (string s followed by the non-overlapping part of t)

3. No overlap: If no overlap exists, concatenate the strings: s + t

Main Algorithm:

1. Generate all permutations: Use permutations((a, b, c)) to generate all 6 possible orderings of the three strings.

2. Process each permutation: For each ordering (a, b, c):

   • First merge a and b: temp = f(a, b)
   • Then merge the result with c: s = f(temp, c)
   • This gives us the merged string for this particular ordering

3. Track the optimal result: Compare each merged string s with the current best answer:

   • If ans is empty (first iteration), set ans = s
   • If len(s) < len(ans), update ans to s (shorter is better)
   • If len(s) == len(ans) and s < ans, update ans to s (same length but lexicographically smaller)

4. Return the result: After checking all 6 permutations, return the optimal string stored in ans.

The time complexity is O(n²) for each merge operation (where n is the length of the strings), and since we perform a constant number of merges (6 permutations × 2 merges each), the overall complexity remains manageable for typical string lengths.

Example Walkthrough

Let's walk through the solution with a concrete example where a = "abc", b = "bca", and c = "aab".

Step 1: Understanding the merge function f(s, t)

First, let's see how the merge function works with f("abc", "bca"):

• Check if "abc" contains "bca" → No
• Check if "bca" contains "abc" → No
• Look for overlap between end of "abc" and start of "bca":
  • Check if last 3 chars of "abc" ("abc") match first 3 chars of "bca" ("bca") → No
  • Check if last 2 chars of "abc" ("bc") match first 2 chars of "bca" ("bc") → Yes!
  • Return "abc" + "bca"[2:] = "abc" + "a" = "abca"

Step 2: Try all 6 permutations

Let's trace through each permutation:

1. Order (a, b, c) = ("abc", "bca", "aab")

   • Merge "abc" and "bca": f("abc", "bca") = "abca" (as shown above)
   • Merge "abca" and "aab": f("abca", "aab")
     • "abca" contains "aab"? No. "aab" contains "abca"? No
     • Check overlaps: "a" at end of "abca" matches "a" at start of "aab"
     • Result: "abca" + "ab" = "abcaab" (length 6)

2. Order (a, c, b) = ("abc", "aab", "bca")

   • Merge "abc" and "aab": f("abc", "aab") = "aabc" (overlap "ab")
   • Merge "aabc" and "bca": f("aabc", "bca") = "aabca" (overlap "bc")
   • Result: "aabca" (length 5)

3. Order (b, a, c) = ("bca", "abc", "aab")

   • Merge "bca" and "abc": f("bca", "abc") = "bcabc" (overlap "a")
   • Merge "bcabc" and "aab": f("bcabc", "aab") = "aabcabc" (no overlap)
   • Result: "aabcabc" (length 7)

4. Order (b, c, a) = ("bca", "aab", "abc")

   • Merge "bca" and "aab": f("bca", "aab") = "bcaaab" (no overlap)
   • Merge "bcaaab" and "abc": f("bcaaab", "abc") = "bcaaabc" (overlap "ab")
   • Result: "bcaaabc" (length 7)

5. Order (c, a, b) = ("aab", "abc", "bca")

   • Merge "aab" and "abc": f("aab", "abc") = "aabc" (overlap "ab")
   • Merge "aabc" and "bca": f("aabc", "bca") = "aabca" (overlap "bc")
   • Result: "aabca" (length 5)

6. Order (c, b, a) = ("aab", "bca", "abc")

   • Merge "aab" and "bca": f("aab", "bca") = "aabca" (overlap "b")
   • Merge "aabca" and "abc": f("aabca", "abc")
     • "aabca" already contains "abc" (at position 1)
     • Result: "aabca" (length 5)

Step 3: Select the optimal result

From all permutations:

• Length 5: "aabca" (appears 3 times)
• Length 6: "abcaab"
• Length 7: "aabcabc", "bcaaabc"

The shortest length is 5, and all three occurrences give us "aabca". We can verify this contains all three strings:

• "abc" appears at index 1: "aabca"
• "bca" appears at index 2: "aabca"
• "aab" appears at index 0: "aabca"

Therefore, the answer is "aabca".

Solution Implementation

Time and Space Complexity

Time Complexity: O(n^2)

The algorithm iterates through all 6 permutations of the three strings (constant factor). For each permutation, it calls function f twice. Within function f:

• The substring checks s in t and t in s take O(n^2) time in the worst case using standard string matching
• The loop runs at most min(m, n) iterations, which is O(n), and each iteration performs string slicing and comparison operations that take O(n) time
• String concatenation operations take O(n) time

Therefore, the dominant operation is the substring checking with O(n^2) complexity, making the overall time complexity O(n^2), where n is the maximum length of the three strings.

Space Complexity: O(n)

The space usage includes:

• The ans variable storing a string of length at most 3n in the worst case: O(n)
• Temporary string s created in each iteration: O(n)
• String slicing operations create new strings: O(n)
• The permutations generator uses constant extra space as it generates permutations one at a time

The space complexity is O(n), where n is the maximum length of the three strings.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Overlap Detection Logic

A common mistake is incorrectly implementing the overlap detection between two strings. Developers often make errors in:

• Using wrong slice indices (e.g., first[:overlap_length] instead of first[-overlap_length:])
• Not properly handling the concatenation after finding an overlap
• Checking overlaps in the wrong direction

Example of incorrect implementation:

# WRONG: Checking wrong parts of strings
if first[:overlap_length] == second[:overlap_length]:  # Both from start!
    return first + second[overlap_length:]

# CORRECT: End of first should match beginning of second
if first[-overlap_length:] == second[:overlap_length]:
    return first + second[overlap_length:]

2. Not Considering All Permutations

Some developers might try to optimize prematurely by only checking certain orders or assuming a greedy approach will work. This fails because the optimal order depends on the specific overlaps between strings.

Example scenario where order matters:

• a = "abc", b = "bcd", c = "cde"
• Order (a,b,c) gives: "abcde" (length 5)
• Order (c,b,a) gives: "cdeabcd" (length 7)

Solution: Always check all 6 permutations as the code does.

3. Forgetting the Containment Check

A critical optimization that's easy to miss is checking whether one string already contains another. Without this check, the algorithm might produce unnecessarily long results.

Example of the issue:

# WITHOUT containment check
def merge_two_strings(first, second):
    # Only checking overlaps
    for overlap_length in range(min(len(first), len(second)), 0, -1):
        if first[-overlap_length:] == second[:overlap_length]:
            return first + second[overlap_length:]
    return first + second

# If first="abcdef" and second="cde", this returns "abcdefcde" (length 9)
# But "cde" is already in "abcdef", so we should just return "abcdef" (length 6)

4. Incorrect Lexicographical Comparison

When comparing strings of equal length, developers might forget to check for lexicographical ordering or implement it incorrectly.

Incorrect approach:

# WRONG: Only considering length
if len(merged_string) < len(result):
    result = merged_string

# CORRECT: Also consider lexicographical order for same length
if (result == "" or 
    len(merged_string) < len(result) or 
    (len(merged_string) == len(result) and merged_string < result)):
    result = merged_string

5. Off-by-One Errors in Range

Using incorrect range bounds when checking overlaps is a frequent error:

Wrong:

# Missing potential overlaps by starting from wrong index
for overlap_length in range(min(first_len, second_len) - 1, 0, -1):  # Off by one!

Correct:

# Check all possible overlaps from maximum to minimum
for overlap_length in range(min(first_len, second_len), 0, -1):

Prevention Tips:

1. Test with edge cases where strings are substrings of each other
2. Verify overlap logic with simple examples manually
3. Use debug prints to trace the merging process
4. Test with strings that have different optimal orderings
5. Include test cases where lexicographical ordering matters