Find the Shortest Superstring II - Solution & Explanation

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.