2800. Shortest String That Contains Three Strings Solution

Q: Is Shortest String That Contains Three Strings easy or hard?

Shortest String That Contains Three Strings is classified as Medium difficulty on LeetCode. The challenge is recognizing that only six permutations exist and implementing correct overlap merging. Once that insight is clear, the rest of the solution is straightforward string manipulation.

Q: Shortest String That Contains Three Strings Python/Java solution

In Python or Java, generate all permutations of the three input strings and repeatedly merge them using maximum overlap logic. For each pair, check if one string already contains the other; otherwise find the largest suffix-prefix match and append only the remaining part. After evaluating all permutations, return the shortest and lexicographically smallest result.

Q: How to solve Shortest String That Contains Three Strings in O(n)?

A strict O(n) solution is not typical because overlap detection between two arbitrary strings may require scanning multiple prefix-suffix lengths. The common optimized approach runs in O(n^2) by checking overlaps directly. With more advanced string algorithms like rolling hash or KMP, the overlap detection can approach O(n), but the standard interview solution remains the O(n^2) greedy merge.

Q: What is the best approach for Shortest String That Contains Three Strings?

The most practical solution enumerates all 6 permutations of the three strings and greedily merges them using maximum prefix-suffix overlap. For each pair of strings, compute the largest overlap where the suffix of the first matches the prefix of the second. Build a merged candidate for each permutation and choose the shortest, breaking ties lexicographically. This runs in about O(n^2) time where n is the maximum string length.

Q: Is Shortest String That Contains Three Strings asked at Google/Amazon/Meta?

Problems involving shortest superstrings and substring overlap frequently appear in interviews at companies like Google, Amazon, and Meta. This specific LeetCode problem focuses on the simplified case of three strings, making it a common medium-level question to test string manipulation and greedy reasoning.

Q: What data structure is used in Shortest String That Contains Three Strings?

The problem primarily uses string operations and permutation enumeration. Implementations often rely on arrays or lists to generate permutations and standard string methods like substring checks and concatenation. Some advanced solutions add memoization tables for dynamic programming states.

Q: What is the time complexity of Shortest String That Contains Three Strings?

The greedy permutation solution runs in O(n^2) time because each merge operation checks overlaps between two strings up to length n. Since there are only 6 permutations of three strings, the constant factor is small. Space complexity is O(n) for storing merged strings.

The 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.

Return a string denoting the answer to the problem.

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.

Example 1:

Input: a = "abc", b = "bca", c = "aaa"
Output: "aaabca"
Explanation:  We show that "aaabca" contains all the given strings: a = ans[2...4], b = ans[3..5], c = ans[0..2]. It can be shown that the length of the resulting string would be at least 6 and "aaabca" is the lexicographically smallest one.

Example 2:

Input: a = "ab", b = "ba", c = "aba"
Output: "aba"
Explanation: We show that the string "aba" contains all the given strings: a = ans[0..1], b = ans[1..2], c = ans[0..2]. Since the length of c is 3, the length of the resulting string would be at least 3. It can be shown that "aba" is the lexicographically smallest one.

Constraints:

1 <= a.length, b.length, c.length <= 100
a, b, c consist only of lowercase English letters.

Approach overview

Problem Overview: You are given three strings a, b, and c. Build the shortest possible string that contains all three as substrings. If multiple answers have the same length, return the lexicographically smallest one.

The core challenge is minimizing redundant characters when combining the strings. If the suffix of one string overlaps with the prefix of another, you should merge them instead of concatenating blindly.

Approach 1: Greedy Overlap with Permutation Enumeration (O(n^2) time, O(n) space)

This approach tries every ordering of the three strings (there are only 3! = 6 permutations). For each order, merge strings one by one using maximum overlap. To merge two strings x and y, first check if y already exists inside x. If not, iterate from the largest possible overlap length down to 0 and match the suffix of x with the prefix of y. Append only the non-overlapping part.

Because each overlap check may scan up to the string length, merging costs O(n^2) in the worst case. After generating a merged string for each permutation, choose the shortest result and break ties using lexicographical comparison. The small constant (only six permutations) keeps the solution efficient in practice. This method relies heavily on careful string manipulation and simple greedy decisions about overlaps.

Approach 2: Dynamic Programming with Memoization (O(n^2 * k!) time, O(n * k) space)

A more structured solution models the problem as merging strings while tracking which ones have already been used. Use a bitmask to represent the chosen strings and memoize the best merged result for each state. For each transition, attempt to append a remaining string using the same maximum-overlap merge routine.

The memoization avoids recomputing the best merged result for identical states. While the search space is small for three strings, this approach demonstrates how the idea generalizes to more strings. It combines dynamic programming with substring overlap computation.

Recommended for interviews: The greedy permutation solution is what most interviewers expect. Enumerating all six orders shows you recognize the small input size, and the overlap merge demonstrates practical string manipulation. Mentioning the DP formulation shows deeper understanding, but implementing the greedy overlap method quickly and correctly is usually enough to pass the interview.

Approach 1: Greedy Approach with Overlap

This approach involves finding the overlap between every pair of strings and combining them. We calculate the minimum possible overlap to form the shortest possible string including all strings as substrings, checking all permutations of the order of a, b, and c.

Python

from itertools import permutations

def overlap(a, b):
    max_overlap = 0
    for i in range(1, min(len(a), len(b)) + 1):
        if a[-i:] == b[:i]:
            max_overlap = i
    return max_overlap

def merge(a, b):
    o = overlap(a, b)
    return a + b[o:]

def solve(a, b, c):
    best = 'z' * (len(a) + len(b) + len(c))
    for perm in permutations([a, b, c]):
        combined = merge(merge(perm[0], perm[1]), perm[2])
        if len(combined) < len(best) or (len(combined) == len(best) and combined < best):
            best = combined
    return best

# Example usage
print(solve("abc", "bca", "aaa"))

Java

import java.util.Arrays;

public class Solution {
    public static int overlap(String a, String b) {
        int maxOverlap = 0;
        int lenA = a.length();
        int lenB = b.length();
        for (int i = 1; i <= lenA && i <= lenB; i++) {
            if (a.substring(lenA - i).equals(b.substring(0, i))) {
                maxOverlap = i;
            }
        }
        return maxOverlap;
    }

    public static String merge(String a, String b) {
        int o = overlap(a, b);
        return a + b.substring(o);
    }

    public static String solve(String a, String b, String c) {
        String[] order = {a, b, c};
        String best = "z";
        Arrays.sort(order);
        do {
            String res1 = merge(order[0], order[1]);
            String res2 = merge(res1, order[2]);
            if (res2.length() < best.length() || (res2.length() == best.length() && res2.compareTo(best) < 0)) {
                best = res2;
            }
        } while (nextPermutation(order));
        return best;
    }

    public static boolean nextPermutation(String[] array) {
        int i = array.length - 2;
        while (i >= 0 && array[i].compareTo(array[i + 1]) >= 0) {
            i--;
        }
        if (i >= 0) {
            int j = array.length - 1;
            while (array[j].compareTo(array[i]) <= 0) {
                j--;
            }
            String temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        } else {
            return false;
        }
        int start = i + 1, end = array.length - 1;
        while (start < end) {
            String temp = array[start];
            array[start] = array[end];
            array[end] = temp;
            start++;
            end--;
        }
        return true;
    }

    public static void main(String[] args) {
        String a = "abc", b = "bca", c = "aaa";
        System.out.println(solve(a, b, c));
    }
}

C++

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int overlap(const string &a, const string &b) {
    int max_overlap = 0;
    int len_a = a.size();
    int len_b = b.size();
    for (int i = 1; i <= len_a && i <= len_b; i++) {
        if (a.substr(len_a - i) == b.substr(0, i)) {
            max_overlap = i;
        }
    }
    return max_overlap;
}

string merge(const string &a, const string &b) {
    int o = overlap(a, b);
    return a + b.substr(o);
}

string solve(const string &a, const string &b, const string &c) {
    vector<string> permutations = {a, b, c};
    string best = "z";
    do {
        string combined1 = merge(permutations[0], permutations[1]);
        string combined2 = merge(combined1, permutations[2]);
        if (combined2.length() < best.length() || (combined2.length() == best.length() && combined2 < best)) {
            best = combined2;
        }
    } while (next_permutation(permutations.begin(), permutations.end()));
    return best;
}

int main() {
    string a = "abc", b = "bca", c = "aaa";
    cout << solve(a, b, c) << endl;
    return 0;
}

JavaScript

function overlap(a, b) {
    let maxOverlap = 0;
    for (let i = 1; i <= a.length && i <= b.length; i++) {
        if (a.slice(-i) === b.slice(0, i)) {
            maxOverlap = i;
        }
    }
    return maxOverlap;
}

function merge(a, b) {
    const o = overlap(a, b);
    return a + b.slice(o);
}

function solve(a, b, c) {
    const perms = [[a, b, c], [a, c, b], [b, a, c], [b, c, a], [c, a, b], [c, b, a]];
    let best = 'z'.repeat(a.length + b.length + c.length);
    for (const perm of perms) {
        const combined1 = merge(perm[0], perm[1]);
        const combined2 = merge(combined1, perm[2]);
        if (combined2.length < best.length || (combined2.length === best.length && combined2 < best)) {
            best = combined2;
        }
    }
    return best;
}

console.log(solve("abc", "bca", "aaa"));

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

int overlap(const char *a, const char *b) {
    int max_overlap = 0;
    int len_a = strlen(a);
    int len_b = strlen(b);
    for (int i = 1; i <= len_a && i <= len_b; i++) {
        if (strncmp(a + len_a - i, b, i) == 0) {
            max_overlap = i;
        }
    }
    return max_overlap;
}

void merge(char *result, const char *a, const char *b) {
    int o = overlap(a, b);
    strcpy(result, a);
    strcat(result, b + o);
}

char *solve(const char *a, const char *b, const char *c) {
    char first[300], second[300], third[300];
    char *res = malloc(300);
    char *best = malloc(300);
    strcpy(best, "z"); // lexicographically largest

    const char *order[6][3] = {
        {a, b, c}, {a, c, b},
        {b, a, c}, {b, c, a},
        {c, a, b}, {c, b, a}
    };

    for (int i = 0; i < 6; i++) {
        merge(first, order[i][0], order[i][1]);
        merge(second, first, order[i][2]);
        if (strlen(second) < strlen(best) || (strlen(second) == strlen(best) && strcmp(second, best) < 0)) {
            strcpy(best, second);
        }
    }
    free(res);
    return best;
}

int main() {
    const char *a = "abc";
    const char *b = "bca";
    const char *c = "aaa";
    char *result = solve(a, b, c);
    printf("%s\n", result);
    free(result);
    return 0;
}

using System;

public class Solution {
    public static int Overlap(string a, string b) {
        int maxOverlap = 0;
        int lenA = a.Length, lenB = b.Length;
        for (int i = 1; i <= lenA && i <= lenB; i++) {
            if (a.Substring(lenA - i) == b.Substring(0, i)) {
                maxOverlap = i;
            }
        }
        return maxOverlap;
    }

    public static string Merge(string a, string b) {
        int o = Overlap(a, b);
        return a + b.Substring(o);
    }

    public static string Solve(string a, string b, string c) {
        string[] order = {a, b, c};
        string best = new string('z', 300);

        Array.Sort(order);
        do {
            string combined1 = Merge(order[0], order[1]);
            string combined2 = Merge(combined1, order[2]);
            if (combined2.Length < best.Length || (combined2.Length == best.Length && combined2.CompareTo(best) < 0)) {
                best = combined2;
            }
        } while (NextPermutation(order));
        return best;
    }

    public static bool NextPermutation(string[] array) {
        int i = array.Length - 2;
        while (i >= 0 && string.Compare(array[i], array[i + 1]) >= 0) {
            i--;
        }
        if (i >= 0) {
            int j = array.Length - 1;
            while (string.Compare(array[j], array[i]) <= 0) {
                j--;
            }
            string temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        } else {
            return false;
        }
        Array.Reverse(array, i + 1, array.Length - (i + 1));
        return true;
    }

    public static void Main(string[] args) {
        string a = "abc", b = "bca", c = "aaa";
        Console.WriteLine(Solve(a, b, c));
    }
}

In this Python solution, itertools' permutations generate possible orderings of a, b, and c. It calculates overlaps, concatenates strings accordingly, and finds the best length (or lexicographically smallest) combination.

Complexity

Time Complexity: O(n^3) due to permutations calculations and overlaps.
Space Complexity: O(n) for merged string storage.

Try this approach in the editor

Approach 2: Dynamic Programming with Memoization

This approach uses dynamic programming to compute the overlap between all strings while storing intermediate results to avoid redundant calculations. This approach aims to build the shortest possible string from the combinations, utilizing memoized overlap results to improve efficiency.

Python

def overlap(a, b, dp=None):
    if dp is None:
        dp = [[-1] * (len(b) + 1) for _ in range(len(a) + 1)]

    lenA, lenB = len(a), len(b)
    if dp[lenA][lenB] != -1:
        return dp[lenA][lenB]

    max_overlap = 0
    for i in range(1, min(lenA, lenB) + 1):
        if a[-i:] == b[:i]:
            max_overlap = i

    dp[lenA][lenB] = max_overlap
    return max_overlap


def merge(a, b, dp):
    o = overlap(a, b, dp)
    return a + b[o:]


def least_length(a, b, c):
    dp = [[-1] * 101 for _ in range(101)]
    ab, bc, ca = merge(a, b, dp), merge(b, c, dp), merge(c, a, dp)
    abc, bac, bca = merge(ab, c, dp), merge(bc, a, dp), merge(ca, b, dp)
    return min(abc, bac, bca)


# Example usage
print(least_length("abc", "bca", "aaa"))

Java

import java.util.*;

public class Solution {
    static int[][] dp = new int[101][101];

    static {
        for (int[] row : dp)
            Arrays.fill(row, -1);
    }

    public static int overlap(String a, String b) {
        int lenA = a.length();
        int lenB = b.length();
        if (dp[lenA][lenB] != -1) return dp[lenA][lenB];

        int maxOverlap = 0;
        for (int i = 1; i <= lenA && i <= lenB; i++) {
            if (a.substring(lenA - i).equals(b.substring(0, i))) {
                maxOverlap = i;
            }
        }
        dp[lenA][lenB] = maxOverlap;
        return maxOverlap;
    }

    public static String merge(String a, String b) {
        int o = overlap(a, b);
        return a + b.substring(o);
    }

    public static String least_length(String a, String b, String c) {
        String ab = merge(a, b);
        String abc = merge(ab, c);

        String bc = merge(b, c);
        String bac = merge(bc, a);

        String ca = merge(c, a);
        String bca = merge(ca, b);

        return Collections.min(Arrays.asList(abc, bac, bca));
    }

    public static void main(String[] args) {
        String a = "abc", b = "bca", c = "aaa";
        System.out.println(least_length(a, b, c));
    }
}

C++

#include <iostream>
#include <vector>
#include <string>
#include <cstring>

using namespace std;

vector<vector<int>> dp(101, vector<int>(101, -1));

int overlap(const string &a, const string &b) {
    int lenA = a.size(), lenB = b.size();
    if (dp[lenA][lenB] != -1) return dp[lenA][lenB];

    int maxOverlap = 0;
    for (int i = 1; i <= lenA && i <= lenB; i++) {
        if (a.substr(lenA - i) == b.substr(0, i)) {
            maxOverlap = i;
        }
    }
    dp[lenA][lenB] = maxOverlap;
    return maxOverlap;
}

string merge(const string &a, const string &b) {
    int o = overlap(a, b);
    return a + b.substr(o);
}

string least_length(const string &a, const string &b, const string &c) {
    string ab = merge(a, b);
    string abc = merge(ab, c);

    string bc = merge(b, c);
    string bac = merge(bc, a);

    string ca = merge(c, a);
    string bca = merge(ca, b);

    return min({abc, bac, bca});
}

int main() {
    memset(&dp[0][0], -1, 101 * 101 * sizeof(int));
    string a = "abc", b = "bca", c = "aaa";
    cout << least_length(a, b, c) << endl;
    return 0;
}

JavaScript

function overlap(a, b, dp) {
    const lenA = a.length, lenB = b.length;
    if (dp[lenA][lenB] !== undefined) return dp[lenA][lenB];

    let maxOverlap = 0;
    for (let i = 1; i <= lenA && i <= lenB; i++) {
        if (a.slice(-i) === b.slice(0, i)) {
            maxOverlap = i;
        }
    }
    dp[lenA][lenB] = maxOverlap;
    return maxOverlap;
}

function merge(a, b, dp) {
    const o = overlap(a, b, dp);
    return a + b.slice(o);
}

function leastLength(a, b, c) {
    const dp = Array.from({ length: 101 }, () => Array(101));
    const ab = merge(a, b, dp);
    const bc = merge(b, c, dp);
    const ca = merge(c, a, dp);
    const abc = merge(ab, c, dp);
    const bac = merge(bc, a, dp);
    const bca = merge(ca, b, dp);
    return [abc, bac, bca].sort()[0];
}

console.log(leastLength('abc', 'bca', 'aaa'));

#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <stdalign.h>

#define MAX_STR 100

int dp[MAX_STR][MAX_STR];

int overlap(char *a, char *b) {
    int lenA = strlen(a), lenB = strlen(b);
    if (dp[lenA][lenB] != -1) return dp[lenA][lenB];

    int maxOverlap = 0;
    for (int i = 1; i <= lenA && i <= lenB; i++) {
        if (strncmp(a + lenA - i, b, i) == 0) {
            maxOverlap = i;
        }
    }
    dp[lenA][lenB] = maxOverlap;
    return maxOverlap;
}

void merge(char *res, char *a, char *b) {
    int o = overlap(a, b);
    strcpy(res, a);
    strcat(res, b + o);
}

char *least_length(char *a, char *b, char *c) {
    char ab[300], bc[300], ca[300];
    char abc[300], bac[300], bca[300];
    char *results[] = {abc, bac, bca};

    merge(ab, a, b);
    merge(abc, ab, c);

    merge(bc, b, c);
    merge(bac, bc, a);

    merge(ca, c, a);
    merge(bca, ca, b);

    char *best = abc;
    for (int i = 1; i < 3; i++) {
        if (strlen(results[i]) < strlen(best) || (strlen(results[i]) == strlen(best) && strcmp(results[i], best) < 0)) {
            best = results[i];
        }
    }

    return best;
}

int main() {
    memset(dp, -1, sizeof dp);
    char *a = "abc", *b = "bca", *c = "aaa";
    printf("%s\n", least_length(a, b, c));
    return 0;
}

using System;

public class Solution {
    static int[,] dp = new int[101, 101];

    static Solution() {
        for (int i = 0; i < 101; i++)
            for (int j = 0; j < 101; j++)
                dp[i, j] = -1;
    }

    public static int Overlap(string a, string b) {
        int lenA = a.Length, lenB = b.Length;
        if (dp[lenA, lenB] != -1) return dp[lenA, lenB];

        int maxOverlap = 0;
        for (int i = 1; i <= lenA && i <= lenB; i++) {
            if (a.Substring(lenA - i) == b.Substring(0, i)) {
                maxOverlap = i;
            }
        }
        dp[lenA, lenB] = maxOverlap;
        return maxOverlap;
    }

    public static string Merge(string a, string b) {
        int o = Overlap(a, b);
        return a + b.Substring(o);
    }

    public static string LeastLength(string a, string b, string c) {
        string ab = Merge(a, b);
        string abc = Merge(ab, c);

        string bc = Merge(b, c);
        string bac = Merge(bc, a);

        string ca = Merge(c, a);
        string bca = Merge(ca, b);

        return new[]{abc, bac, bca}.Min();
    }

    public static void Main(string[] args) {
        string a = "abc", b = "bca", c = "aaa";
        Console.WriteLine(LeastLength(a, b, c));
    }
}

Python's version uses a memoized table for tracking overlaps with entry (lenA, lenB). The main objective is reducing recomputation through saved values for overlap functionality.

Complexity

Time Complexity: O(n^3), streamlined by caching with dynamic programming.
Space Complexity: O(n^2), reflecting the dynamic table size.

Try this approach in the editor

Approach 3: Enumeration

We enumerate all permutations of the three strings, and for each permutation, we merge the three strings to find the shortest string with the smallest lexicographical order.

The time complexity is O(n^2), and the space complexity is O(n). Where n is the maximum length of the three strings.

TypeScript

function minimumString(a: string, b: string, c: string): string {
    const f = (s: string, t: string): string => {
        if (s.includes(t)) {
            return s;
        }
        if (t.includes(s)) {
            return t;
        }
        const m = s.length;
        const n = t.length;
        for (let i = Math.min(m, n); i > 0; --i) {
            if (s.slice(-i) === t.slice(0, i)) {
                return s + t.slice(i);
            }
        }
        return s + t;
    };
    const s: string[] = [a, b, c];
    const perm: number[][] = [
        [0, 1, 2],
        [0, 2, 1],
        [1, 0, 2],
        [1, 2, 0],
        [2, 0, 1],
        [2, 1, 0],
    ];
    let ans = '';
    for (const [i, j, k] of perm) {
        const t = f(f(s[i], s[j]), s[k]);
        if (ans === '' || t.length < ans.length || (t.length === ans.length && t < ans)) {
            ans = t;
        }
    }
    return ans;
}

func minimumString(a string, b string, c string) string {
	f := func(s, t string) string {
		if strings.Contains(s, t) {
			return s
		}
		if strings.Contains(t, s) {
			return t
		}
		m, n := len(s), len(t)
		for i := min(m, n); i > 0; i-- {
			if s[m-i:] == t[:i] {
				return s + t[i:]
			}
		}
		return s + t
	}
	s := [3]string{a, b, c}
	ans := ""
	for _, p := range [][]int{{0, 1, 2}, {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, {2, 0, 1}, {2, 1, 0}} {
		i, j, k := p[0], p[1], p[2]
		t := f(f(s[i], s[j]), s[k])
		if ans == "" || len(t) < len(ans) || (len(t) == len(ans) && t < ans) {
			ans = t
		}
	}
	return ans
}

Rust

impl Solution {
    fn f(s1: String, s2: String) -> String {
        if s1.contains(&s2) {
            return s1;
        }
        if s2.contains(&s1) {
            return s2;
        }
        for i in 0..s1.len() {
            let s = &s1[i..];
            if s2.starts_with(s) {
                let n = s.len();
                return s1 + &s2[n..];
            }
        }
        s1 + s2.as_str()
    }

    pub fn minimum_string(a: String, b: String, c: String) -> String {
        let s = [&a, &b, &c];
        let perm = [
            [0, 1, 2],
            [0, 2, 1],
            [1, 0, 2],
            [1, 2, 0],
            [2, 0, 1],
            [2, 1, 0],
        ];
        let mut ans = String::new();
        for [i, j, k] in perm.iter() {
            let r = Self::f(Self::f(s[*i].clone(), s[*j].clone()), s[*k].clone());
            if ans == "" || r.len() < ans.len() || (r.len() == ans.len() && r < ans) {
                ans = r;
            }
        }
        ans
    }
}

Try this approach in the editor

Approach 4: Enumeration + KMP

We can use the KMP algorithm to optimize the string merging process.

Time complexity is O(n), and space complexity is O(n). Here, n is the sum of the lengths of the three strings.

TypeScript

function minimumString(a: string, b: string, c: string): string {
    const f = (s: string, t: string): string => {
        if (s.includes(t)) {
            return s;
        }
        if (t.includes(s)) {
            return t;
        }
        const p = t + '#' + s + '$';
        const n = p.length;
        const next: number[] = Array(n).fill(0);
        next[0] = -1;
        for (let i = 2, j = 0; i < n; ) {
            if (p[i - 1] === p[j]) {
                next[i++] = ++j;
            } else if (j) {
                j = next[j];
            } else {
                next[i++] = 0;
            }
        }
        return s + t.slice(next[n - 1]);
    };
    const s: string[] = [a, b, c];
    const perm: number[][] = [
        [0, 1, 2],
        [0, 2, 1],
        [1, 0, 2],
        [1, 2, 0],
        [2, 0, 1],
        [2, 1, 0],
    ];
    let ans = '';
    for (const [i, j, k] of perm) {
        const t = f(f(s[i], s[j]), s[k]);
        if (ans === '' || t.length < ans.length || (t.length === ans.length && t < ans)) {
            ans = t;
        }
    }
    return ans;
}

func minimumString(a string, b string, c string) string {
	f := func(s, t string) string {
		if strings.Contains(s, t) {
			return s
		}
		if strings.Contains(t, s) {
			return t
		}
		p := t + "#" + s + "$"
		n := len(p)
		next := make([]int, n)
		next[0] = -1
		for i, j := 2, 0; i < n; {
			if p[i-1] == p[j] {
				j++
				next[i] = j
				i++
			} else if j > 0 {
				j = next[j]
			} else {
				next[i] = 0
				i++
			}
		}
		return s + t[next[n-1]:]
	}
	s := [3]string{a, b, c}
	ans := ""
	for _, p := range [][]int{{0, 1, 2}, {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, {2, 0, 1}, {2, 1, 0}} {
		i, j, k := p[0], p[1], p[2]
		t := f(f(s[i], s[j]), s[k])
		if ans == "" || len(t) < len(ans) || (len(t) == len(ans) && t < ans) {
			ans = t
		}
	}
	return ans
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Greedy Approach with Overlap	Time Complexity: O(n^3) due to permutations calculations and overlaps. Space Complexity: O(n) for merged string storage.
Dynamic Programming with Memoization	Time Complexity: O(n^3), streamlined by caching with dynamic programming. Space Complexity: O(n^2), reflecting the dynamic table size.
Enumeration	–
Enumeration + KMP	–

Complexity analysis

Approach	Time	Space	When to Use
Greedy Overlap with Permutation Enumeration	O(n^2)	O(n)	Best practical solution when only three strings are involved
Dynamic Programming with Memoization	O(n^2 * k!)	O(n * k)	Useful when extending the problem to more strings or demonstrating DP reasoning

Frequently asked questions

Is Shortest String That Contains Three Strings easy or hard?

Shortest String That Contains Three Strings is classified as Medium difficulty on LeetCode. The challenge is recognizing that only six permutations exist and implementing correct overlap merging. Once that insight is clear, the rest of the solution is straightforward string manipulation.

Shortest String That Contains Three Strings Python/Java solution

In Python or Java, generate all permutations of the three input strings and repeatedly merge them using maximum overlap logic. For each pair, check if one string already contains the other; otherwise find the largest suffix-prefix match and append only the remaining part. After evaluating all permutations, return the shortest and lexicographically smallest result.

How to solve Shortest String That Contains Three Strings in O(n)?

A strict O(n) solution is not typical because overlap detection between two arbitrary strings may require scanning multiple prefix-suffix lengths. The common optimized approach runs in O(n^2) by checking overlaps directly. With more advanced string algorithms like rolling hash or KMP, the overlap detection can approach O(n), but the standard interview solution remains the O(n^2) greedy merge.

What is the best approach for Shortest String That Contains Three Strings?

The most practical solution enumerates all 6 permutations of the three strings and greedily merges them using maximum prefix-suffix overlap. For each pair of strings, compute the largest overlap where the suffix of the first matches the prefix of the second. Build a merged candidate for each permutation and choose the shortest, breaking ties lexicographically. This runs in about O(n^2) time where n is the maximum string length.

Is Shortest String That Contains Three Strings asked at Google/Amazon/Meta?

Problems involving shortest superstrings and substring overlap frequently appear in interviews at companies like Google, Amazon, and Meta. This specific LeetCode problem focuses on the simplified case of three strings, making it a common medium-level question to test string manipulation and greedy reasoning.

What data structure is used in Shortest String That Contains Three Strings?

The problem primarily uses string operations and permutation enumeration. Implementations often rely on arrays or lists to generate permutations and standard string methods like substring checks and concatenation. Some advanced solutions add memoization tables for dynamic programming states.

What is the time complexity of Shortest String That Contains Three Strings?

The greedy permutation solution runs in O(n^2) time because each merge operation checks overlaps between two strings up to length n. Since there are only 6 permutations of three strings, the constant factor is small. Space complexity is O(n) for storing merged strings.

Shortest String That Contains Three Strings solution and explanation

The problem

Approach overview

Approach 1: Greedy Approach with Overlap

Approach 2: Dynamic Programming with Memoization

Approach 3: Enumeration

Approach 4: Enumeration + KMP

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Shortest String That Contains Three Strings solution and explanation

The problem

Approach overview

Approach 1: Greedy Approach with Overlap

Approach 2: Dynamic Programming with Memoization

Approach 3: Enumeration

Approach 4: Enumeration + KMP

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems