Shortest String That Contains Three Strings - Solution & Explanation

Q: Is Shortest String That Contains Three Strings easy or hard?

Shortest String That Contains Three Strings is classified as Medium difficulty on LeetCode. The challenge is recognizing that only six permutations exist and implementing correct overlap merging. Once that insight is clear, the rest of the solution is straightforward string manipulation.

Q: Shortest String That Contains Three Strings Python/Java solution

In Python or Java, generate all permutations of the three input strings and repeatedly merge them using maximum overlap logic. For each pair, check if one string already contains the other; otherwise find the largest suffix-prefix match and append only the remaining part. After evaluating all permutations, return the shortest and lexicographically smallest result.

Q: How to solve Shortest String That Contains Three Strings in O(n)?

A strict O(n) solution is not typical because overlap detection between two arbitrary strings may require scanning multiple prefix-suffix lengths. The common optimized approach runs in O(n^2) by checking overlaps directly. With more advanced string algorithms like rolling hash or KMP, the overlap detection can approach O(n), but the standard interview solution remains the O(n^2) greedy merge.

Q: What is the best approach for Shortest String That Contains Three Strings?

The most practical solution enumerates all 6 permutations of the three strings and greedily merges them using maximum prefix-suffix overlap. For each pair of strings, compute the largest overlap where the suffix of the first matches the prefix of the second. Build a merged candidate for each permutation and choose the shortest, breaking ties lexicographically. This runs in about O(n^2) time where n is the maximum string length.

Q: Is Shortest String That Contains Three Strings asked at Google/Amazon/Meta?

Problems involving shortest superstrings and substring overlap frequently appear in interviews at companies like Google, Amazon, and Meta. This specific LeetCode problem focuses on the simplified case of three strings, making it a common medium-level question to test string manipulation and greedy reasoning.

Q: What data structure is used in Shortest String That Contains Three Strings?

The problem primarily uses string operations and permutation enumeration. Implementations often rely on arrays or lists to generate permutations and standard string methods like substring checks and concatenation. Some advanced solutions add memoization tables for dynamic programming states.

Q: What is the time complexity of Shortest String That Contains Three Strings?

The greedy permutation solution runs in O(n^2) time because each merge operation checks overlaps between two strings up to length n. Since there are only 6 permutations of three strings, the constant factor is small. Space complexity is O(n) for storing merged strings.

MediumString Greedy Enumeration25 min readAsked at: Google, Bloomberg, De Shaw

Practice this problem

Problem Statement

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.

Approach Overview

Problem Overview: You are given three strings a, b, and c. Build the shortest possible string that contains all three as substrings. If multiple answers have the same length, return the lexicographically smallest one.

The core challenge is minimizing redundant characters when combining the strings. If the suffix of one string overlaps with the prefix of another, you should merge them instead of concatenating blindly.

Approach 1: Greedy Overlap with Permutation Enumeration (O(n^2) time, O(n) space)

This approach tries every ordering of the three strings (there are only 3! = 6 permutations). For each order, merge strings one by one using maximum overlap. To merge two strings x and y, first check if y already exists inside x. If not, iterate from the largest possible overlap length down to 0 and match the suffix of x with the prefix of y. Append only the non-overlapping part.

Because each overlap check may scan up to the string length, merging costs O(n^2) in the worst case. After generating a merged string for each permutation, choose the shortest result and break ties using lexicographical comparison. The small constant (only six permutations) keeps the solution efficient in practice. This method relies heavily on careful string manipulation and simple greedy decisions about overlaps.

Approach 2: Dynamic Programming with Memoization (O(n^2 * k!) time, O(n * k) space)

A more structured solution models the problem as merging strings while tracking which ones have already been used. Use a bitmask to represent the chosen strings and memoize the best merged result for each state. For each transition, attempt to append a remaining string using the same maximum-overlap merge routine.

The memoization avoids recomputing the best merged result for identical states. While the search space is small for three strings, this approach demonstrates how the idea generalizes to more strings. It combines dynamic programming with substring overlap computation.

Recommended for interviews: The greedy permutation solution is what most interviewers expect. Enumerating all six orders shows you recognize the small input size, and the overlap merge demonstrates practical string manipulation. Mentioning the DP formulation shows deeper understanding, but implementing the greedy overlap method quickly and correctly is usually enough to pass the interview.

Approach 1: Greedy Approach with Overlap

This approach involves finding the overlap between every pair of strings and combining them. We calculate the minimum possible overlap to form the shortest possible string including all strings as substrings, checking all permutations of the order of a, b, and c.

The solution attempts to find maximum overlap between two strings to concatenate them efficiently. We find permutations of a, b, and c to ensure all orders are checked, calculate the overlap, and combine accordingly.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O((n + m + l)^2) for each permutation due to overlap calculation.
Space Complexity: O(n + m + l) for storing combined results and intermediate strings.

Try this approach in the editor →

Approach 2: Dynamic Programming with Memoization

This approach uses dynamic programming to compute the overlap between all strings while storing intermediate results to avoid redundant calculations. This approach aims to build the shortest possible string from the combinations, utilizing memoized overlap results to improve efficiency.

The C solution initializes a memoization table to store intermediate overlap results, thus minimizing redundant calculations. This assists in efficiently constructing the overlapping substrings.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n^3) with reduced constant factors due to memoization.
Space Complexity: O(n^2) for storing DP overlap values.

Try this approach in the editor →

Approach 3: Enumeration

We enumerate all permutations of the three strings, and for each permutation, we merge the three strings to find the shortest string with the smallest lexicographical order.

The time complexity is O(n^2), and the space complexity is O(n). Where n is the maximum length of the three strings.

Code

Python Java C++Go TypeScript Rust

Python

Java

C++

TypeScript

Rust

Try this approach in the editor →

Approach 4: Enumeration + KMP

We can use the KMP algorithm to optimize the string merging process.

Time complexity is O(n), and space complexity is O(n). Here, n is the sum of the lengths of the three strings.

Code

Python Java C++Go TypeScript

Python

Java

C++

TypeScript

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Greedy Approach with Overlap	Time Complexity: O((n + m + l)^2) for each permutation due to overlap calculation. Space Complexity: O(n + m + l) for storing combined results and intermediate strings.
Dynamic Programming with Memoization	Time Complexity: O(n^3) with reduced constant factors due to memoization. Space Complexity: O(n^2) for storing DP overlap values.
Enumeration	—
Enumeration + KMP	—

Detailed Complexity Analysis

Approach	Time	Space	When to Use
Greedy Overlap with Permutation Enumeration	O(n^2)	O(n)	Best practical solution when only three strings are involved
Dynamic Programming with Memoization	O(n^2 * k!)	O(n * k)	Useful when extending the problem to more strings or demonstrating DP reasoning

Video Solution

Leetcode Weekly contest 356 - Medium - Shortest String That Contains Three Strings • Prakhar Agrawal • 2,532 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Shortest String That Contains Three Strings easy or hard?

Shortest String That Contains Three Strings is classified as Medium difficulty on LeetCode. The challenge is recognizing that only six permutations exist and implementing correct overlap merging. Once that insight is clear, the rest of the solution is straightforward string manipulation.

Shortest String That Contains Three Strings Python/Java solution

In Python or Java, generate all permutations of the three input strings and repeatedly merge them using maximum overlap logic. For each pair, check if one string already contains the other; otherwise find the largest suffix-prefix match and append only the remaining part. After evaluating all permutations, return the shortest and lexicographically smallest result.

How to solve Shortest String That Contains Three Strings in O(n)?

A strict O(n) solution is not typical because overlap detection between two arbitrary strings may require scanning multiple prefix-suffix lengths. The common optimized approach runs in O(n^2) by checking overlaps directly. With more advanced string algorithms like rolling hash or KMP, the overlap detection can approach O(n), but the standard interview solution remains the O(n^2) greedy merge.

What is the best approach for Shortest String That Contains Three Strings?

The most practical solution enumerates all 6 permutations of the three strings and greedily merges them using maximum prefix-suffix overlap. For each pair of strings, compute the largest overlap where the suffix of the first matches the prefix of the second. Build a merged candidate for each permutation and choose the shortest, breaking ties lexicographically. This runs in about O(n^2) time where n is the maximum string length.

Is Shortest String That Contains Three Strings asked at Google/Amazon/Meta?

Problems involving shortest superstrings and substring overlap frequently appear in interviews at companies like Google, Amazon, and Meta. This specific LeetCode problem focuses on the simplified case of three strings, making it a common medium-level question to test string manipulation and greedy reasoning.

What data structure is used in Shortest String That Contains Three Strings?

The problem primarily uses string operations and permutation enumeration. Implementations often rely on arrays or lists to generate permutations and standard string methods like substring checks and concatenation. Some advanced solutions add memoization tables for dynamic programming states.

What is the time complexity of Shortest String That Contains Three Strings?

The greedy permutation solution runs in O(n^2) time because each merge operation checks overlaps between two strings up to length n. Since there are only 6 permutations of three strings, the constant factor is small. Space complexity is O(n) for storing merged strings.

Ready to solve this problem?

Practice Shortest String That Contains Three Strings with our built-in code editor and test cases.

Practice on FleetCode

Shortest Common Supersequence

Problem Info

DifficultyMedium

Acceptance32.2%

Approaches4

Reading time25 min

Asked at

Google Bloomberg De Shaw

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Greedy Approach with Overlap

Code

Complexity

Approach 2: Dynamic Programming with Memoization

Code

Complexity

Approach 3: Enumeration

Code

Approach 4: Enumeration + KMP

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents