You are given two strings, s1 and s2. Return the shortest possible string that contains both s1 and s2 as substrings. If there are multiple valid answers, return any one of them.
A substring is a contiguous sequence of characters within a string.
Example 1:
Input: s1 = "aba", s2 = "bab"
Output: "abab"
Explanation:
"abab" is the shortest string that contains both "aba" and "bab" as substrings.
Example 2:
Input: s1 = "aa", s2 = "aaa"
Output: "aaa"
Explanation:
"aa" is already contained within "aaa", so the shortest superstring is "aaa".
Constraints:
1 <= s1.length <= 1001 <= s2.length <= 100s1 and s2 consist of lowercase English letters only.Problem Overview: You are given two strings and need to build the shortest possible string that contains both as substrings. The key challenge is avoiding redundant characters when the suffix of one string overlaps with the prefix of the other.
Approach 1: Direct Concatenation Baseline (O(n + m) time, O(n + m) space)
The simplest idea is to concatenate the strings in both possible orders: a + b and b + a. This guarantees a valid superstring because both original strings appear as substrings. However, it ignores potential overlaps between the suffix of one string and the prefix of the other, often producing a longer result than necessary. Time complexity is O(n + m) for building the candidate strings, and space complexity is O(n + m). This baseline helps verify correctness but does not produce the optimal result when overlaps exist.
Approach 2: Enumerate Overlapping Parts (O((n + m)^2) time, O(n + m) space)
The optimal strategy checks how much the two strings overlap. Specifically, compare the suffix of a with the prefix of b, and the suffix of b with the prefix of a. Iterate over all possible overlap lengths and keep the maximum match. If the suffix of one string matches the prefix of the other, you only append the non-overlapping portion instead of the entire second string.
For example, if a = "abcde" and b = "cdef", the overlap is "cde". Instead of abcdecdef, you produce abcdef. The algorithm checks overlaps from length 1 up to min(len(a), len(b)). Perform this check in both directions (a → b and b → a) and return the shorter resulting string.
This approach relies purely on string comparison operations and works well for moderate input sizes. The worst-case time complexity is O((n + m)^2) due to repeated substring comparisons, while space complexity remains O(n + m) for constructing the resulting superstring. Problems like this commonly appear in string manipulation and greedy reasoning, where maximizing overlap directly minimizes the final length.
Recommended for interviews: Enumerating overlaps is the expected solution. It demonstrates that you recognize the overlap structure instead of blindly concatenating strings. Mention the baseline concatenation first to show you considered simpler possibilities, then implement the overlap check. Interviewers typically want to see clear iteration over possible suffix–prefix matches and correct handling of both concatenation orders.
We can construct the shortest string containing both s1 and s2 as substrings by enumerating the overlapping parts of the two strings.
Our goal is to build the shortest string that contains both s1 and s2 as substrings. Since substrings must be contiguous, we try to overlap the suffix of one string with the prefix of the other, thereby reducing the total length when concatenating.
Specifically, there are several cases:
s1 is a substring of s2, then s2 itself satisfies the condition, so just return s2; vice versa as well.s1 matches a prefix of s2, and concatenate after finding the maximum overlap.s1 matches a suffix of s2, and concatenate after finding the maximum overlap.s1 + s2.We try both concatenation orders and return the shorter one (if the lengths are equal, either is acceptable).
The time complexity is O(n^2) and the space complexity is O(n), where n is the maximum length of s1 and s2.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Concatenation Baseline | O(n + m) | O(n + m) | Quick baseline to guarantee a valid superstring without considering overlaps |
| Enumerate Overlapping Parts | O((n + m)^2) | O(n + m) | General solution that minimizes length by maximizing suffix–prefix overlap |
Practice Find the Shortest Superstring II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor