Find the Shortest Superstring II - Practice Coding Problems

Find the Shortest Superstring II - Problem

String Easy

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.

Input & Output

Example 1 — Overlap Case

$ Input: s1 = "abc", s2 = "bcd"

› Output: "abcd"

💡 Note: The suffix "bc" of s1 overlaps with the prefix "bc" of s2, so we merge them as "abc" + "d" = "abcd"

Example 2 — Containment Case

$ Input: s1 = "hello", s2 = "ell"

› Output: "hello"

💡 Note: s2 "ell" is already contained in s1 "hello", so the shortest superstring is just "hello"

Example 3 — No Overlap

$ Input: s1 = "cat", s2 = "dog"

› Output: "catdog"

💡 Note: No overlap exists between the strings, so we concatenate them as "cat" + "dog" = "catdog"

Constraints

1 ≤ s1.length, s2.length ≤ 1000
s1 and s2 consist of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

Two strings s1 and s2

Find Overlap

Check suffix-prefix overlaps

Merge

Create shortest superstring

Key Takeaway

🎯 Key Insight: Finding maximum overlap between string endings minimizes the total superstring length

Asked in

G Google 25 M Microsoft 20 a Amazon 15

The key insight is to find the maximum overlap between the suffix of one string and the prefix of another. The optimal approach checks for containment first, then finds overlaps in both directions to minimize the total length. Time: O(n × m), Space: O(n + m)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Combinations	O(n + m)	O(n + m)	Try all possible ways to combine the two strings
Optimized - Find Maximum Overlap	O(n × m)	O(n + m)	Find maximum overlap between strings to minimize total length

Brute Force - Try All Combinations — Algorithm Steps

Step 1: Check if s1 contains s2 or vice versa
Step 2: Try concatenating s1+s2 and s2+s1
Step 3: Return the shortest valid superstring

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Containment

See if one string contains the other

Try Concatenations

Create s1+s2 and s2+s1

Choose Shorter

Return the shorter result

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* solution(char* s1, char* s2) {
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    
    // Check if one string contains the other
    if (strstr(s1, s2) != NULL) {
        char* result = malloc((len2 + 1) * sizeof(char));
        strcpy(result, s2);
        return result;
    }
    if (strstr(s2, s1) != NULL) {
        char* result = malloc((len1 + 1) * sizeof(char));
        strcpy(result, s1);
        return result;
    }
    
    // Try both concatenations and return the shorter one
    char* option1 = malloc((len1 + len2 + 1) * sizeof(char));
    char* option2 = malloc((len1 + len2 + 1) * sizeof(char));
    strcpy(option1, s1);
    strcat(option1, s2);
    strcpy(option2, s2);
    strcat(option2, s1);
    
    if (strlen(option1) <= strlen(option2)) {
        free(option2);
        return option1;
    } else {
        free(option1);
        return option2;
    }
}

int main() {
    char s1[1001], s2[1001];
    fgets(s1, sizeof(s1), stdin);
    fgets(s2, sizeof(s2), stdin);
    s1[strcspn(s1, "\n")] = 0;
    s2[strcspn(s2, "\n")] = 0;
    
    char* result = solution(s1, s2);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + m)

String containment check and concatenation operations

✓ Linear Growth

Space Complexity

O(n + m)

Space for creating result strings

⚡ Linearithmic Space

21.3K Views

Medium Frequency

~15 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler