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.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.
Java
C++
Go
TypeScript
Practice Find the Shortest Superstring II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor