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 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.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, c consist only of lowercase English letters.The key idea is to build the shortest superstring that contains all three given strings as substrings. Since there are only three strings, we can efficiently enumerate all permutations of their ordering and attempt to merge them greedily.
For each order, merge two strings by finding the maximum overlap between the suffix of the first string and the prefix of the second. If one string is already a substring of the other, we simply keep the longer one. After merging the first two strings, repeat the process with the third string.
Among all generated candidates, choose the string with the minimum length. If multiple results have the same length, select the lexicographically smallest one. This works because the number of permutations is small (3! = 6), allowing a straightforward enumeration combined with greedy overlap checks.
The overall complexity mainly depends on computing overlaps between strings of length n.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Permutation + Greedy Overlap Merge | O(6 * n^2) | O(n) |
Ashish Pratap Singh
Use these hints if you're stuck. Try solving on your own first.
Think about how you can generate all possible strings that contain all three input strings as substrings. Can you come up with an efficient algorithm to do this?
Check all permutations of the words a, b, and c. For each permutation, begin by appending some letters to the end of the first word to form the second word. Then, proceed to add more letters to generate the third word.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
The order in which strings are merged affects the final overlap and resulting length. By checking all six permutations of the three strings, we guarantee that we evaluate every possible merging order. This ensures we find the shortest valid superstring.
Yes, variations of shortest superstring and string overlap problems appear in technical interviews at major tech companies. They test knowledge of greedy thinking, string manipulation, and handling permutations efficiently. Practicing this problem helps strengthen those interview skills.
No advanced data structures are required for this problem. Simple string operations and helper functions to compute prefix-suffix overlap are sufficient. Since there are only three strings, brute-force permutation with greedy merging is efficient enough.
The optimal approach enumerates all permutations of the three strings and greedily merges them using maximum suffix-prefix overlap. For each ordering, build a candidate superstring and choose the shortest result. If multiple results have the same length, return the lexicographically smallest one.