Is Find the Shortest Superstring II easy or hard?

Find the Shortest Superstring II is generally categorized as an easy string problem. The core idea is recognizing that maximizing suffix–prefix overlap minimizes the final string length, which leads to a straightforward enumeration solution.

Find the Shortest Superstring II Python/Java solution

A typical Python or Java implementation iterates over overlap lengths from 1 to min(len(a), len(b)). When the suffix of one string equals the prefix of the other, append only the non-overlapping portion. Perform the check in both directions and return the shorter constructed string.

How to solve Find the Shortest Superstring II in O(n)?

Strict O(n) is generally not achievable with naive substring comparisons because each overlap check may compare multiple characters. Practical implementations enumerate overlap lengths and compare characters, leading to O((n + m)^2) time. More advanced string techniques like rolling hash or KMP-style prefix matching can reduce repeated comparisons but add implementation complexity.

What is the best approach for Find the Shortest Superstring II?

The most effective method is enumerating suffix–prefix overlaps between the two strings. Check every possible overlap length where the suffix of one string matches the prefix of the other, then append only the remaining portion. Evaluate both concatenation orders and return the shorter result. This guarantees the minimum-length superstring.

Is Find the Shortest Superstring II asked at Google/Amazon/Meta?

String overlap and shortest superstring style problems appear in interviews at companies like Google, Amazon, and Meta, especially in simplified forms. Interviewers use them to evaluate string manipulation skills, edge case handling, and the ability to reason about overlaps.

What data structure is used in Find the Shortest Superstring II?

The problem primarily uses basic string operations such as substring comparison and concatenation. No complex data structures are required; the algorithm relies on iterating through possible overlaps and building the resulting string.

What is the time complexity of Find the Shortest Superstring II?

The overlap enumeration approach runs in O((n + m)^2) time in the worst case because multiple substring comparisons are performed while checking overlap lengths. Space complexity is O(n + m) for constructing the resulting superstring.

Description Hints 1 Solution Video 26:31

3571. Find the Shortest Superstring II

Easy48.8% acceptancePremium elsewhere, free here

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 <= 100
1 <= s2.length <= 100
s1 and s2 consist of lowercase English letters only.

Topics

String

Hints open one at a time

Hint 1

Check for the maximum suffix of one string that matches a prefix of the other (in both directions) and merge accordingly.

26:31

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

3571. Find the Shortest Superstring II

Topics

Hints open one at a time

Similar problems