LeetCode 2800 - Shortest String That Contains Three Strings

Difficulty: 🟡 Medium
Topics: String, Greedy, Enumeration

Solution

Problem Understanding

The problem asks us to construct a string that contains three given strings a, b, and c as substrings while minimizing its length. If multiple strings satisfy the minimum length condition, the lexicographically smallest one must be returned. In other words, the solution must be the shortest possible string that embeds all three input strings, and among all strings of that minimal length, it must come first in alphabetical order.

The inputs a, b, and c are strings of lowercase English letters, each with a length between 1 and 100. These constraints indicate that we cannot afford an exponential approach that generates all possible superstrings naively, but we can consider strategies that examine combinations intelligently.

Important edge cases include situations where one string is already a substring of another, which may allow the shortest superstring to simply be the longest of them. Another tricky case arises when there are overlapping prefixes and suffixes between strings, which can reduce the total length if combined optimally.

Approaches

Brute Force

A brute-force approach would generate all permutations of the three strings, attempt to merge them in all possible orders by checking overlaps, and then select the shortest result. To merge two strings, we would look for the largest overlap where the suffix of the first string matches the prefix of the second string, append the remainder of the second string, and repeat for all strings. Although this guarantees correctness, it requires evaluating all permutations and combinations of overlaps, which is inefficient, though feasible for three strings due to the factorial number of permutations being small (3! = 6). However, naive substring checks could add overhead.

Optimal Approach

The key insight is that with only three strings, we can afford to enumerate all permutations of string orderings (six possibilities) and for each, merge the strings greedily by their maximum overlap. To merge two strings efficiently, we compute the longest suffix-prefix match. If one string is already contained in another, we can skip it. After processing all permutations, we select the resulting string with the shortest length, and in case of ties, the lexicographically smallest one. This approach leverages combinatorial reasoning combined with greedy string merging to be both correct and efficient.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^3 * 6)	O(n)	Merge all permutations with substring checks; correct but redundant operations
Optimal	O(n^2 * 6)	O(n)	Greedy merge by overlap for each permutation; handles substring containment and selects shortest lexicographical string

Algorithm Walkthrough

Define a function to merge two strings x and y by maximal overlap. Start by checking if y is a substring of x, in which case return x. Otherwise, find the largest suffix of x that matches the prefix of y and append the remaining part of y to x. If no overlap exists, simply concatenate x + y.
Enumerate all six permutations of the three strings a, b, and c. For each permutation (s1, s2, s3), merge s1 and s2 using the function above to get merged12. Then merge merged12 with s3 to get merged123.
Track the minimal merged string encountered so far. If a newly generated string has a smaller length than the current minimum, replace it. If lengths are equal, select the lexicographically smaller one.
After evaluating all permutations, return the tracked minimal string.

Why it works: Since we consider all permutations of the three strings and always merge greedily with maximal overlap, we are guaranteed to find the globally shortest superstring. Lexicographical ordering is ensured by comparing ties, fulfilling the problem requirements.

Python Solution

from itertools import permutations

class Solution:
    def minimumString(self, a: str, b: str, c: str) -> str:
        def merge(x: str, y: str) -> str:
            if y in x:
                return x
            for i in range(len(x)):
                if x[i:] == y[:len(x)-i]:
                    return x + y[len(x)-i:]
            return x + y
        
        strings = [a, b, c]
        res = None
        
        for perm in permutations(strings):
            merged = merge(merge(perm[0], perm[1]), perm[2])
            if res is None or len(merged) < len(res) or (len(merged) == len(res) and merged < res):
                res = merged
        
        return res

The implementation first defines a helper function merge that performs maximal overlap merging. Using itertools.permutations, all possible string orderings are evaluated. The solution tracks the minimum string in both length and lexicographic order. Finally, it returns the optimal merged string.

Go Solution

package main

import (
	"fmt"
	"strings"
)

func minimumString(a string, b string, c string) string {
	merge := func(x, y string) string {
		if strings.Contains(x, y) {
			return x
		}
		for i := 0; i < len(x); i++ {
			if len(x)-i <= len(y) && x[i:] == y[:len(x)-i] {
				return x + y[len(x)-i:]
			}
		}
		return x + y
	}

	stringsArr := []string{a, b, c}
	perms := [][]int{
		{0, 1, 2}, {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, {2, 0, 1}, {2, 1, 0},
	}

	var res string
	for _, p := range perms {
		merged := merge(merge(stringsArr[p[0]], stringsArr[p[1]]), stringsArr[p[2]])
		if res == "" || len(merged) < len(res) || (len(merged) == len(res) && merged < res) {
			res = merged
		}
	}
	return res
}

In Go, we handle permutations manually since the standard library does not provide a permutation generator. The merge function is similar to Python’s, with explicit length checks to avoid index overflows. Tracking the minimum string follows the same logic.

Worked Examples

Example 1: a = "abc", b = "bca", c = "aaa"

Step	Strings Merged	Result
Merge "abc" + "bca"	overlap "bc"	"abca"
Merge "abca" + "aaa"	overlap "a"	"aaabca"

Result: "aaabca"

Example 2: a = "ab", b = "ba", c = "aba"

Step	Strings Merged	Result
Merge "ab" + "ba"	overlap "b"	"aba"
Merge "aba" + "aba"	substring exists	"aba"

Result: "aba"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n^2)	Each merge operation may check up to O(n^2) characters, done 6 times for permutations.
Space	O(n)	Merged string storage; no extra large data structures.

The algorithm is efficient because n ≤ 100, and the fixed 6 permutations make it tractable. Overlap checks are quadratic in string length, which is acceptable at this scale.

Test Cases

sol = Solution()

# Provided examples
assert sol.minimumString("abc", "bca", "aaa") == "aaabca"  # Example 1
assert sol.minimumString("ab", "ba", "aba") == "aba"       # Example 2

# Edge and additional cases
assert sol.minimumString("a", "a", "a") == "a"              # All identical
assert sol.minimumString("abc", "abc", "abc") == "abc"     # One string covers all
assert sol.minimumString("abc", "def", "ghi") == "abcdefghi"  # No overlaps
assert sol.minimumString("abc", "bc", "c") == "abc"        # Smaller strings are substrings
assert sol.minimumString("xyz", "yzx", "zxy") == "xyzxy"   # Overlaps require careful merging

Test	Why
"abc","bca","aaa"	Overlaps and lexicographical choice
"ab","ba","aba"	Substring fully contained
"a","a","a"	Identical strings edge case
"abc","abc","abc"	Redundant substrings
"abc","def","ghi"	No overlaps, concatenation required
"abc","bc","c"	Smaller strings already contained
"xyz","yzx","zxy"	Complex overlapping

Edge Cases

The first edge case is when one string is completely contained within another. Without checking containment, a naive merge might unnecessarily lengthen the result. The merge function explicitly handles this by returning the larger string if one contains the other.

The second edge case occurs when two strings partially overlap at multiple positions. For example, "ababa" and "baba" overlap at more than one index. The algorithm ensures the **