Shortest String That Contains Three Strings
MedPrompt
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
ais lexicographically smaller than a stringb(of the same length) if in the first position whereaandbdiffer, stringahas a letter that appears earlier in the alphabet than the corresponding letter inb. - 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 <= 100a,b,cconsist 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
candidatesto store the results. - For each permutation
(s1, s2, s3):- Merge
s1ands2to get an intermediate stringtemp. The merge operation finds the maximum overlap between the end of the first string and the beginning of the second. - Merge
tempands3to get the final candidate string. - Add the final candidate to the
candidateslist.
- Merge
- Iterate through the
candidateslist 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.
class Solution { public String minimumString(String a, String b, String c) { String[] arr = {a, b, c}; String res = ""; int[][] permutations = { {0, 1, 2}, {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, {2, 0, 1}, {2, 1, 0} }; for (int[] p : permutations) { String s1 = arr[p[0]]; String s2 = arr[p[1]]; String s3 = arr[p[2]]; String current = merge(merge(s1, s2), s3); if (res.isEmpty() || current.length() < res.length() || (current.length() == res.length() && current.compareTo(res) < 0)) { res = current; } } return res; } // Merges s2 onto the end of s1 with max overlap private String merge(String s1, String s2) { if (s1.contains(s2)) { return s1; } for (int i = Math.min(s1.length(), s2.length()); i > 0; i--) { if (s1.endsWith(s2.substring(0, i))) { return s1 + s2.substring(i); } } return s1 + s2; }}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.
Solutions
Solution
class 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 ; } }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.