3571. Find the Shortest Superstring II 🔒

Description

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.

Solutions

Solution 1: Enumerate Overlapping Parts

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:

1. Containment: If s1 is a substring of s2, then s2 itself satisfies the condition, so just return s2; vice versa as well.
2. s1 concatenated before s2: Enumerate whether a suffix of s1 matches a prefix of s2, and concatenate after finding the maximum overlap.
3. s2 concatenated before s1: Enumerate whether a prefix of s1 matches a suffix of s2, and concatenate after finding the maximum overlap.
4. No overlap: If there is no overlap between the suffix/prefix of the two strings, simply return 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.

Python3JavaC++GoTypeScript

class Solution:
    def shortestSuperstring(self, s1: str, s2: str) -> str:
        m, n = len(s1), len(s2)
        if m > n:
            return self.shortestSuperstring(s2, s1)
        if s1 in s2:
            return s2
        for i in range(m):
            if s2.startswith(s1[i:]):
                return s1[:i] + s2
            if s2.endswith(s1[: m - i]):
                return s2 + s1[m - i :]
        return s1 + s2

class Solution {
    public String shortestSuperstring(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        if (m > n) {
            return shortestSuperstring(s2, s1);
        }
        if (s2.contains(s1)) {
            return s2;
        }
        for (int i = 0; i < m; i++) {
            if (s2.startsWith(s1.substring(i))) {
                return s1.substring(0, i) + s2;
            }
            if (s2.endsWith(s1.substring(0, m - i))) {
                return s2 + s1.substring(m - i);
            }
        }
        return s1 + s2;
    }
}

class Solution {
public:
    string shortestSuperstring(string s1, string s2) {
        int m = s1.size(), n = s2.size();
        if (m > n) {
            return shortestSuperstring(s2, s1);
        }
        if (s2.find(s1) != string::npos) {
            return s2;
        }
        for (int i = 0; i < m; ++i) {
            if (s2.find(s1.substr(i)) == 0) {
                return s1.substr(0, i) + s2;
            }
            if (s2.rfind(s1.substr(0, m - i)) == s2.size() - (m - i)) {
                return s2 + s1.substr(m - i);
            }
        }
        return s1 + s2;
    }
};

func shortestSuperstring(s1 string, s2 string) string {
    m, n := len(s1), len(s2)

    if m > n {
        return shortestSuperstring(s2, s1)
    }

    if strings.Contains(s2, s1) {
        return s2
    }

    for i := 0; i < m; i++ {
        if strings.HasPrefix(s2, s1[i:]) {
            return s1[:i] + s2
        }
        if strings.HasSuffix(s2, s1[:m-i]) {
            return s2 + s1[m-i:]
        }
    }

    return s1 + s2
}

function shortestSuperstring(s1: string, s2: string): string {
    const m = s1.length,
        n = s2.length;

    if (m > n) {
        return shortestSuperstring(s2, s1);
    }

    if (s2.includes(s1)) {
        return s2;
    }

    for (let i = 0; i < m; i++) {
        if (s2.startsWith(s1.slice(i))) {
            return s1.slice(0, i) + s2;
        }
        if (s2.endsWith(s1.slice(0, m - i))) {
            return s2 + s1.slice(m - i);
        }
    }

    return s1 + s2;
}

Comments