Shortest String That Contains Three Strings

Shortest String That Contains Three Strings - Problem

Given three strings a, b, and c, your task is to find a string that has the minimum length and contains all three strings as substrings.

If there are multiple such strings, return the lexicographically smallest one.

Notes:

A string a is lexicographically smaller than a string b (of the same length) if in the first position where a and b differ, string a has a letter that appears earlier in the alphabet than the corresponding letter in b.
A substring is a contiguous sequence of characters within a string.

Input & Output

Example 1 — Basic Case

$ Input: a = "abc", b = "bca", c = "cab"

› Output: "abcab"

💡 Note: One optimal arrangement is abc + cab (overlapping 'c' and 'ab') to get "abcab". This contains all three strings: abc (0-2), bca (1-3), cab (2-4). Length is 5.

Example 2 — No Overlap

$ Input: a = "abc", b = "def", c = "ghi"

› Output: "abcdefghi"

💡 Note: No overlaps possible between these strings, so we concatenate in lexicographical order: abc + def + ghi = "abcdefghi". Length is 9.

Example 3 — One String Contains Others

$ Input: a = "a", b = "aa", c = "aaa"

› Output: "aaa"

💡 Note: String "aaa" already contains both "a" and "aa" as substrings, so it's the optimal superstring with length 3.

Constraints

1 ≤ a.length, b.length, c.length ≤ 50
a, b, and c consist of lowercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Input

Three strings: abc, bca, cab

Find Overlaps

Look for overlapping parts between strings

Output

Shortest superstring: abcab (length 5)

Key Takeaway

🎯 Key Insight: Try all arrangements and maximize overlaps to find the shortest superstring

Asked in

G Google 35 a Amazon 28 M Microsoft 22

The key insight is to try all permutations of the three strings and find optimal overlaps between adjacent strings in each arrangement. The brute force approach generates all 6 permutations and merges with maximum overlap. Time: O(n³), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Try All Permutations	O(n³)	O(n)	Generate all possible arrangements of the three strings and find the shortest superstring
Optimized Overlap Detection	O(n²)	O(1)	Pre-compute all possible overlaps and use them to efficiently merge strings

Try All Permutations — Algorithm Steps

Step 1: Generate all 6 permutations of strings a, b, c
Step 2: For each permutation, find optimal merge by checking overlaps
Step 3: Keep track of shortest result, breaking ties lexicographically

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Permutations

Try all 6 ways to arrange the three strings

Find Overlaps

For each arrangement, merge with maximum overlap

Select Best

Choose shortest result, breaking ties lexicographically

Code -

solution.c — C

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

char* mergeTwo(const char* s1, const char* s2) {
    int len1 = strlen(s1), len2 = strlen(s2);
    int maxOverlap = len1 < len2 ? len1 : len2;
    
    for (int i = maxOverlap; i > 0; i--) {
        if (strncmp(s1 + len1 - i, s2, i) == 0) {
            char* result = malloc(len1 + len2 - i + 1);
            strcpy(result, s1);
            strcat(result, s2 + i);
            return result;
        }
    }
    
    char* result = malloc(len1 + len2 + 1);
    strcpy(result, s1);
    strcat(result, s2);
    return result;
}

char* mergeThree(const char* x, const char* y, const char* z) {
    char* temp = mergeTwo(x, y);
    char* result = mergeTwo(temp, z);
    free(temp);
    return result;
}

char* solution(char* a, char* b, char* c) {
    char* strings[3] = {a, b, c};
    int perms[6][3] = {{0,1,2}, {0,2,1}, {1,0,2}, {1,2,0}, {2,0,1}, {2,1,0}};
    char* candidates[6];
    
    for (int i = 0; i < 6; i++) {
        candidates[i] = mergeThree(strings[perms[i][0]], strings[perms[i][1]], strings[perms[i][2]]);
    }
    
    // Find minimum length
    int minLen = strlen(candidates[0]);
    for (int i = 1; i < 6; i++) {
        int len = strlen(candidates[i]);
        if (len < minLen) minLen = len;
    }
    
    // Find lexicographically smallest among shortest
    char* best = NULL;
    for (int i = 0; i < 6; i++) {
        if (strlen(candidates[i]) == minLen) {
            if (best == NULL || strcmp(candidates[i], best) < 0) {
                best = candidates[i];
            }
        }
    }
    
    // Create final result
    char* result = malloc(strlen(best) + 1);
    strcpy(result, best);
    
    // Clean up
    for (int i = 0; i < 6; i++) {
        free(candidates[i]);
    }
    
    return result;
}

int main() {
    char a[1001], b[1001], c[1001];
    
    fgets(a, sizeof(a), stdin);
    fgets(b, sizeof(b), stdin);
    fgets(c, sizeof(c), stdin);
    
    // Remove newlines
    a[strcspn(a, "\n")] = 0;
    b[strcspn(b, "\n")] = 0;
    c[strcspn(c, "\n")] = 0;
    
    char* result = solution(a, b, c);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

For each of 6 permutations, we check overlaps which can take O(n²) time in worst case

⚠ Quadratic Growth

Space Complexity

O(n)

Store candidate results and temporary strings during merging

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~25 min Avg. Time

890 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

Try All Permutations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler