Shortest String That Contains Three Strings

Med

#2507Time: O(L^2), where L is the maximum length of the input strings. The number of permutations is constant (6). Each permutation requires two `merge` operations. The `merge` operation is dominated by string operations like `contains` or the overlap-checking loop, which can take up to O(L^2) time as string lengths can grow.Space: O(L), where L is the maximum length of the input strings. We store a constant number of candidate strings, and the maximum length of a candidate string is at most 3L.1 company

Patterns

Greedy Enumeration

Data structures

String

Companies

DE Shaw

Prompt

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.

Return a string denoting the answer to the problem.

Notes

A string a is lexicographically smaller than a string b (of the same length) if in the first position where a and b differ, string a has a letter that appears earlier in the alphabet than the corresponding letter in b.
A substring is a contiguous sequence of characters within a string.

Example 1:

Input: a = "abc", b = "bca", c = "aaa"
Output: "aaabca"
Explanation:  We show that "aaabca" contains all the given strings: a = ans[2...4], b = ans[3..5], c = ans[0..2]. It can be shown that the length of the resulting string would be at least 6 and "aaabca" is the lexicographically smallest one.

Example 2:

Input: a = "ab", b = "ba", c = "aba"
Output: "aba"
Explanation: We show that the string "aba" contains all the given strings: a = ans[0..1], b = ans[1..2], c = ans[0..2]. Since the length of c is 3, the length of the resulting string would be at least 3. It can be shown that "aba" is the lexicographically smallest one.

Constraints:

1 <= a.length, b.length, c.length <= 100
a, b, c consist only of lowercase English letters.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach considers all possible orderings (permutations) of the three strings a, b, and c. For each ordering, it merges the strings sequentially and generates a candidate superstring. Finally, it compares all generated candidates to find the shortest and lexicographically smallest one.

Algorithm

Create a list of the three input strings: [a, b, c].
Generate all 6 permutations of these strings.
Initialize an empty list candidates to store the results.
For each permutation (s1, s2, s3):
- Merge s1 and s2 to get an intermediate string temp. The merge operation finds the maximum overlap between the end of the first string and the beginning of the second.
- Merge temp and s3 to get the final candidate string.
- Add the final candidate to the candidates list.
Iterate through the candidates list to find the string that is shortest. If there's a tie in length, choose the one that comes first lexicographically.
Return the best candidate found.

Walkthrough

This method systematically explores all possible ways to combine the three strings. Since the order of merging matters (e.g., merging a then b can be different from b then a), we need to consider all permutations of the strings a, b, and c.

There are 3! = 6 permutations for three distinct items. We generate a candidate superstring for each of these 6 orderings.

For an ordering (s1, s2, s3), we first merge s1 and s2 into a temporary string, and then merge this temporary string with s3.

The core of this approach is a helper function, merge(str1, str2), which combines two strings by finding the longest suffix of str1 that is also a prefix of str2, thus maximizing the overlap and minimizing the length of the combined string. This function also handles cases where one string is already a substring of the other.

After generating all 6 candidate strings, we iterate through them to find the one with the minimum length. If there are multiple strings with the same minimum length, we select the one that is lexicographically smallest.

1class Solution {2    public String minimumString(String a, String b, String c) {3        String[] arr = {a, b, c};4        String res = "";5 6        int[][] permutations = {7            {0, 1, 2}, {0, 2, 1}, {1, 0, 2},8            {1, 2, 0}, {2, 0, 1}, {2, 1, 0}9        };10 11        for (int[] p : permutations) {12            String s1 = arr[p[0]];13            String s2 = arr[p[1]];14            String s3 = arr[p[2]];15 16            String current = merge(merge(s1, s2), s3);17 18            if (res.isEmpty() || current.length() < res.length() ||19               (current.length() == res.length() && current.compareTo(res) < 0)) {20                res = current;21            }22        }23        return res;24    }25 26    // Merges s2 onto the end of s1 with max overlap27    private String merge(String s1, String s2) {28        if (s1.contains(s2)) {29            return s1;30        }31        for (int i = Math.min(s1.length(), s2.length()); i > 0; i--) {32            if (s1.endsWith(s2.substring(0, i))) {33                return s1 + s2.substring(i);34            }35        }36        return s1 + s2;37    }38}

Complexity

Time

O(L^2), where L is the maximum length of the input strings. The number of permutations is constant (6). Each permutation requires two `merge` operations. The `merge` operation is dominated by string operations like `contains` or the overlap-checking loop, which can take up to O(L^2) time as string lengths can grow.

Space

O(L), where L is the maximum length of the input strings. We store a constant number of candidate strings, and the maximum length of a candidate string is at most 3L.

Trade-offs

Pros

Guaranteed to find the correct answer because it exhaustively checks all possible merge orders.
Relatively straightforward to implement.

Cons

Can be inefficient for cases where one string is a substring of another, as it performs unnecessary merge operations.
Performs a fixed number of computations (12 merges) regardless of whether the input can be simplified.

This approach improves upon the brute-force permutation method by first simplifying the set of strings. It checks if any of the three strings is a substring of another. If a is a substring of b, then any superstring containing b will automatically contain a. Therefore, a can be removed from consideration. After this filtering step, we are left with a smaller set of 'maximal' strings (1, 2, or 3 strings) to merge, which can significantly reduce computation.

Algorithm

Create a Set from a, b, c to get unique strings. Convert back to a List, say uniqueStrings.
Create a new list filteredStrings.
For each string s1 in uniqueStrings:
- Assume s1 is maximal (isMaximal = true).
- For each other string s2 in uniqueStrings:
  - If s1 is a substring of s2 (and s1 is not s2), set isMaximal = false and break.
- If isMaximal is still true, add s1 to filteredStrings.
Now filteredStrings contains the minimal set of strings to combine. Let its size be n.
If n=1, return the only string.
If n=2, compare the two merge orders (merge(s1, s2) and merge(s2, s1)) and return the best result.
If n=3, perform the full 6-permutation check on the original strings and return the best result.

Walkthrough

This approach enhances the previous method by adding an initial filtering step to reduce the number of strings that need to be merged. The key insight is that if a string s1 is a substring of another string s2, any valid superstring that contains s2 will automatically contain s1. Therefore, s1 can be disregarded.

We first filter the initial list of three strings [a, b, c] to create a new list containing only 'maximal' strings—those that are not substrings of any other string in the set.

The problem is then solved based on the number of strings remaining after filtering:

1 string: The single remaining string is the answer.
2 strings: We only need to check two merge orders (s1 then s2, and s2 then s1) and pick the better result.
3 strings: No strings were filtered out. We proceed with the same logic as the brute-force permutation approach, checking all 6 merge orders.

This pre-filtering step can significantly reduce computation, especially in cases like the second example (a="ab", b="ba", c="aba"), where the problem simplifies to finding a superstring for just one string ("aba").

1import java.util.*;2 3class Solution {4    public String minimumString(String a, String b, String c) {5        List<String> strings = new ArrayList<>(Arrays.asList(a, b, c));6        // Use a Set to handle identical inputs, then filter7        List<String> uniqueStrings = new ArrayList<>(new LinkedHashSet<>(strings));8        List<String> filteredList = new ArrayList<>();9 10        if (uniqueStrings.size() < 3) { // If there are duplicates, re-run on unique strings11            if (uniqueStrings.size() == 1) return uniqueStrings.get(0);12            if (uniqueStrings.size() == 2) {13                 return solve(uniqueStrings.get(0), uniqueStrings.get(1));14            }15        }16 17        // Check for substrings18        for (int i = 0; i < strings.size(); i++) {19            boolean isSubstring = false;20            for (int j = 0; j < strings.size(); j++) {21                if (i != j && strings.get(j).contains(strings.get(i))) {22                    isSubstring = true;23                    break;24                }25            }26            if (!isSubstring) {27                filteredList.add(strings.get(i));28            }29        }30        31        // Remove duplicates from filtered list32        filteredList = new ArrayList<>(new LinkedHashSet<>(filteredList));33 34        if (filteredList.isEmpty()) { // e.g., a="a", b="aa", c="aa". 'a' is filtered. 'aa' remains.35            return a.length() < b.length() ? a : b; // Fallback for cases like a="a", b="a"36        }37        if (filteredList.size() == 1) return filteredList.get(0);38        if (filteredList.size() == 2) return solve(filteredList.get(0), filteredList.get(1));39        40        // Fallback to full permutation check on original strings41        return solve(a, b, c);42    }43 44    private String solve(String a, String b, String c) {45        String[] arr = {a, b, c};46        String res = "";47        int[][] permutations = {{0, 1, 2}, {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, {2, 0, 1}, {2, 1, 0}};48        for (int[] p : permutations) {49            String current = merge(merge(arr[p[0]], arr[p[1]]), arr[p[2]]);50            if (res.isEmpty() || current.length() < res.length() || (current.length() == res.length() && current.compareTo(res) < 0)) {51                res = current;52            }53        }54        return res;55    }56 57    private String solve(String s1, String s2) {58        String res1 = merge(s1, s2);59        String res2 = merge(s2, s1);60        if (res1.length() < res2.length()) return res1;61        if (res2.length() < res1.length()) return res2;62        return res1.compareTo(res2) <= 0 ? res1 : res2;63    }64 65    private String merge(String s1, String s2) {66        if (s1.contains(s2)) return s1;67        for (int i = Math.min(s1.length(), s2.length()); i > 0; i--) {68            if (s1.endsWith(s2.substring(0, i))) {69                return s1 + s2.substring(i);70            }71        }72        return s1 + s2;73    }74}

Complexity

Time

O(L^2). The pre-filtering step involves a constant number of substring checks, which take O(L^2) time. The rest of the algorithm is either faster (if strings are filtered out) or has the same O(L^2) complexity as the unoptimized approach.

Space

O(L), where L is the maximum length of the input strings. The space is used for storing the filtered list and candidate strings.

Trade-offs

Pros

More efficient in practice by avoiding redundant computations.
Simplifies the problem for many common cases, such as when one string contains another.

Cons

Slightly more complex to implement due to the initial filtering logic.
The worst-case time complexity is the same as the unoptimized approach if no strings can be filtered out.

Solutions

Solution

1class Solution { public String minimumString ( String a , String b , String c ) { String [] s = { a , b , c }; int [][] perm = { { 0 , 1 , 2 }, { 0 , 2 , 1 }, { 1 , 0 , 2 }, { 1 , 2 , 0 }, { 2 , 1 , 0 }, { 2 , 0 , 1 } }; String ans = "" ; for ( var p : perm ) { int i = p [ 0 ], j = p [ 1 ], k = p [ 2 ]; String t = f ( f ( s [ i ], s [ j ]), s [ k ]); if ( "" . equals ( ans ) || t . length () < ans . length () || ( t . length () == ans . length () && t . compareTo ( ans ) < 0 )) { ans = t ; } } return ans ; } private String f ( String s , String t ) { if ( s . contains ( t )) { return s ; } if ( t . contains ( s )) { return t ; } int m = s . length (), n = t . length (); for ( int i = Math . min ( m , n ); i > 0 ; -- i ) { if ( s . substring ( m - i ). equals ( t . substring ( 0 , i ))) { return s + t . substring ( i ); } } return s + t ; } }

1class Solution { public: string minimumString ( string a , string b , string c ) { vector < string > s = { a , b , c }; vector < vector < int >> perm = { { 0 , 1 , 2 }, { 0 , 2 , 1 }, { 1 , 0 , 2 }, { 1 , 2 , 0 }, { 2 , 1 , 0 }, { 2 , 0 , 1 } }; string ans = "" ; for ( auto & p : perm ) { int i = p [ 0 ], j = p [ 1 ], k = p [ 2 ]; string t = f ( f ( s [ i ], s [ j ]), s [ k ]); if ( ans == "" || t . size () < ans . size () || ( t . size () == ans . size () && t < ans )) { ans = t ; } } return ans ; } string f ( string s , string t ) { if ( s . find ( t ) != string :: npos ) { return s ; } if ( t . find ( s ) != string :: npos ) { return t ; } int m = s . size (), n = t . size (); for ( int i = min ( m , n ); i ; -- i ) { if ( s . substr ( m - i ) == t . substr ( 0 , i )) { return s + t . substr ( i ); } } return s + t ; }; };

1class Solution : def minimumString ( self , a : str , b : str , c : str ) -> str : def f ( s : str , t : str ) -> str : if s in t : return t if t in s : return s m , n = len ( s ), len ( t ) for i in range ( min ( m , n ), 0 , - 1 ): if s [ - i :] == t [: i ]: return s + t [ i :] return s + t ans = "" for a , b , c in permutations (( a , b , c )): s = f ( f ( a , b ), c ) if ans == "" or len ( s ) < len ( ans ) or ( len ( s ) == len ( ans ) and s < ans ): ans = s return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem