# Shortest String That Contains Three Strings
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/shortest-string-that-contains-three-strings)
Canonical: https://scaleengineer.com/dsa/problems/shortest-string-that-contains-three-strings
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Data structures:** String
**Companies:** [DE Shaw](https://scaleengineer.com/companies/de-shaw)
---
## 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**lexicographicallysmallest** 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.

# Approaches
## Brute-Force Permutations
This approach considers all possible orderings (permutations) of the three strings `a`, `b`, and `c`. For each ordering, it merges the strings sequentially and generates a candidate superstring. Finally, it compares all generated candidates to find the shortest and lexicographically smallest one.
**Time:** O(L^2), where L is the maximum length of the input strings. The number of permutations is constant (6). Each permutation requires two `merge` operations. The `merge` operation is dominated by string operations like `contains` or the overlap-checking loop, which can take up to O(L^2) time as string lengths can grow. · **Space:** O(L), where L is the maximum length of the input strings. We store a constant number of candidate strings, and the maximum length of a candidate string is at most 3L.
**Pros:** Guaranteed to find the correct answer because it exhaustively checks all possible merge orders.; Relatively straightforward to implement.
**Cons:** Can be inefficient for cases where one string is a substring of another, as it performs unnecessary merge operations.; Performs a fixed number of computations (12 merges) regardless of whether the input can be simplified.
### Explanation
This method systematically explores all possible ways to combine the three strings. Since the order of merging matters (e.g., merging `a` then `b` can be different from `b` then `a`), we need to consider all permutations of the strings `a`, `b`, and `c`.

There are `3! = 6` permutations for three distinct items. We generate a candidate superstring for each of these 6 orderings.

For an ordering `(s1, s2, s3)`, we first merge `s1` and `s2` into a temporary string, and then merge this temporary string with `s3`.

The core of this approach is a helper function, `merge(str1, str2)`, which combines two strings by finding the longest suffix of `str1` that is also a prefix of `str2`, thus maximizing the overlap and minimizing the length of the combined string. This function also handles cases where one string is already a substring of the other.

After generating all 6 candidate strings, we iterate through them to find the one with the minimum length. If there are multiple strings with the same minimum length, we select the one that is lexicographically smallest.

```java
class Solution {
    public String minimumString(String a, String b, String c) {
        String[] arr = {a, b, c};
        String res = "";

        int[][] permutations = {
            {0, 1, 2}, {0, 2, 1}, {1, 0, 2},
            {1, 2, 0}, {2, 0, 1}, {2, 1, 0}
        };

        for (int[] p : permutations) {
            String s1 = arr[p[0]];
            String s2 = arr[p[1]];
            String s3 = arr[p[2]];

            String current = merge(merge(s1, s2), s3);

            if (res.isEmpty() || current.length() < res.length() ||
               (current.length() == res.length() && current.compareTo(res) < 0)) {
                res = current;
            }
        }
        return res;
    }

    // Merges s2 onto the end of s1 with max overlap
    private String merge(String s1, String s2) {
        if (s1.contains(s2)) {
            return s1;
        }
        for (int i = Math.min(s1.length(), s2.length()); i > 0; i--) {
            if (s1.endsWith(s2.substring(0, i))) {
                return s1 + s2.substring(i);
            }
        }
        return s1 + s2;
    }
}
```
### Algorithm
*   Create a list of the three input strings: `[a, b, c]`.
*   Generate all 6 permutations of these strings.
*   Initialize an empty list `candidates` to store the results.
*   For each permutation `(s1, s2, s3)`:
    *   Merge `s1` and `s2` to get an intermediate string `temp`. The merge operation finds the maximum overlap between the end of the first string and the beginning of the second.
    *   Merge `temp` and `s3` to get the final candidate string.
    *   Add the final candidate to the `candidates` list.
*   Iterate through the `candidates` list to find the string that is shortest. If there's a tie in length, choose the one that comes first lexicographically.
*   Return the best candidate found.

## Optimized Permutations with Substring Pre-filtering
This approach improves upon the brute-force permutation method by first simplifying the set of strings. It checks if any of the three strings is a substring of another. If `a` is a substring of `b`, then any superstring containing `b` will automatically contain `a`. Therefore, `a` can be removed from consideration. After this filtering step, we are left with a smaller set of 'maximal' strings (1, 2, or 3 strings) to merge, which can significantly reduce computation.
**Time:** O(L^2). The pre-filtering step involves a constant number of substring checks, which take O(L^2) time. The rest of the algorithm is either faster (if strings are filtered out) or has the same O(L^2) complexity as the unoptimized approach. · **Space:** O(L), where L is the maximum length of the input strings. The space is used for storing the filtered list and candidate strings.
**Pros:** More efficient in practice by avoiding redundant computations.; Simplifies the problem for many common cases, such as when one string contains another.
**Cons:** Slightly more complex to implement due to the initial filtering logic.; The worst-case time complexity is the same as the unoptimized approach if no strings can be filtered out.
### Explanation
This approach enhances the previous method by adding an initial filtering step to reduce the number of strings that need to be merged. The key insight is that if a string `s1` is a substring of another string `s2`, any valid superstring that contains `s2` will automatically contain `s1`. Therefore, `s1` can be disregarded.

We first filter the initial list of three strings `[a, b, c]` to create a new list containing only 'maximal' strings—those that are not substrings of any other string in the set.

The problem is then solved based on the number of strings remaining after filtering:
*   **1 string:** The single remaining string is the answer.
*   **2 strings:** We only need to check two merge orders (`s1` then `s2`, and `s2` then `s1`) and pick the better result.
*   **3 strings:** No strings were filtered out. We proceed with the same logic as the brute-force permutation approach, checking all 6 merge orders.

This pre-filtering step can significantly reduce computation, especially in cases like the second example (`a="ab", b="ba", c="aba"`), where the problem simplifies to finding a superstring for just one string (`"aba"`).

```java
import java.util.*;

class Solution {
    public String minimumString(String a, String b, String c) {
        List<String> strings = new ArrayList<>(Arrays.asList(a, b, c));
        // Use a Set to handle identical inputs, then filter
        List<String> uniqueStrings = new ArrayList<>(new LinkedHashSet<>(strings));
        List<String> filteredList = new ArrayList<>();

        if (uniqueStrings.size() < 3) { // If there are duplicates, re-run on unique strings
            if (uniqueStrings.size() == 1) return uniqueStrings.get(0);
            if (uniqueStrings.size() == 2) {
                 return solve(uniqueStrings.get(0), uniqueStrings.get(1));
            }
        }

        // Check for substrings
        for (int i = 0; i < strings.size(); i++) {
            boolean isSubstring = false;
            for (int j = 0; j < strings.size(); j++) {
                if (i != j && strings.get(j).contains(strings.get(i))) {
                    isSubstring = true;
                    break;
                }
            }
            if (!isSubstring) {
                filteredList.add(strings.get(i));
            }
        }
        
        // Remove duplicates from filtered list
        filteredList = new ArrayList<>(new LinkedHashSet<>(filteredList));

        if (filteredList.isEmpty()) { // e.g., a="a", b="aa", c="aa". 'a' is filtered. 'aa' remains.
            return a.length() < b.length() ? a : b; // Fallback for cases like a="a", b="a"
        }
        if (filteredList.size() == 1) return filteredList.get(0);
        if (filteredList.size() == 2) return solve(filteredList.get(0), filteredList.get(1));
        
        // Fallback to full permutation check on original strings
        return solve(a, b, c);
    }

    private String solve(String a, String b, String c) {
        String[] arr = {a, b, c};
        String res = "";
        int[][] permutations = {{0, 1, 2}, {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, {2, 0, 1}, {2, 1, 0}};
        for (int[] p : permutations) {
            String current = merge(merge(arr[p[0]], arr[p[1]]), arr[p[2]]);
            if (res.isEmpty() || current.length() < res.length() || (current.length() == res.length() && current.compareTo(res) < 0)) {
                res = current;
            }
        }
        return res;
    }

    private String solve(String s1, String s2) {
        String res1 = merge(s1, s2);
        String res2 = merge(s2, s1);
        if (res1.length() < res2.length()) return res1;
        if (res2.length() < res1.length()) return res2;
        return res1.compareTo(res2) <= 0 ? res1 : res2;
    }

    private String merge(String s1, String s2) {
        if (s1.contains(s2)) return s1;
        for (int i = Math.min(s1.length(), s2.length()); i > 0; i--) {
            if (s1.endsWith(s2.substring(0, i))) {
                return s1 + s2.substring(i);
            }
        }
        return s1 + s2;
    }
}
```
### Algorithm
*   Create a `Set` from `a, b, c` to get unique strings. Convert back to a `List`, say `uniqueStrings`.
*   Create a new list `filteredStrings`.
*   For each string `s1` in `uniqueStrings`:
    *   Assume `s1` is maximal (`isMaximal = true`).
    *   For each other string `s2` in `uniqueStrings`:
        *   If `s1` is a substring of `s2` (and `s1` is not `s2`), set `isMaximal = false` and break.
    *   If `isMaximal` is still true, add `s1` to `filteredStrings`.
*   Now `filteredStrings` contains the minimal set of strings to combine. Let its size be `n`.
*   If `n=1`, return the only string.
*   If `n=2`, compare the two merge orders (`merge(s1, s2)` and `merge(s2, s1)`) and return the best result.
*   If `n=3`, perform the full 6-permutation check on the original strings and return the best result.

# Solutions
### Java

```java
class Solution { public String minimumString ( String a , String b , String c ) { String [] s = { a , b , c }; int [][] perm = { { 0 , 1 , 2 }, { 0 , 2 , 1 }, { 1 , 0 , 2 }, { 1 , 2 , 0 }, { 2 , 1 , 0 }, { 2 , 0 , 1 } }; String ans = "" ; for ( var p : perm ) { int i = p [ 0 ], j = p [ 1 ], k = p [ 2 ]; String t = f ( f ( s [ i ], s [ j ]), s [ k ]); if ( "" . equals ( ans ) || t . length () < ans . length () || ( t . length () == ans . length () && t . compareTo ( ans ) < 0 )) { ans = t ; } } return ans ; } private String f ( String s , String t ) { if ( s . contains ( t )) { return s ; } if ( t . contains ( s )) { return t ; } int m = s . length (), n = t . length (); for ( int i = Math . min ( m , n ); i > 0 ; -- i ) { if ( s . substring ( m - i ). equals ( t . substring ( 0 , i ))) { return s + t . substring ( i ); } } return s + t ; } }
```

### CPP

```cpp
class Solution { public: string minimumString ( string a , string b , string c ) { vector < string > s = { a , b , c }; vector < vector < int >> perm = { { 0 , 1 , 2 }, { 0 , 2 , 1 }, { 1 , 0 , 2 }, { 1 , 2 , 0 }, { 2 , 1 , 0 }, { 2 , 0 , 1 } }; string ans = "" ; for ( auto & p : perm ) { int i = p [ 0 ], j = p [ 1 ], k = p [ 2 ]; string t = f ( f ( s [ i ], s [ j ]), s [ k ]); if ( ans == "" || t . size () < ans . size () || ( t . size () == ans . size () && t < ans )) { ans = t ; } } return ans ; } string f ( string s , string t ) { if ( s . find ( t ) != string :: npos ) { return s ; } if ( t . find ( s ) != string :: npos ) { return t ; } int m = s . size (), n = t . size (); for ( int i = min ( m , n ); i ; -- i ) { if ( s . substr ( m - i ) == t . substr ( 0 , i )) { return s + t . substr ( i ); } } return s + t ; }; };
```

### Python

```python
class Solution : def minimumString ( self , a : str , b : str , c : str ) -> str : def f ( s : str , t : str ) -> str : if s in t : return t if t in s : return s m , n = len ( s ), len ( t ) for i in range ( min ( m , n ), 0 , - 1 ): if s [ - i :] == t [: i ]: return s + t [ i :] return s + t ans = "" for a , b , c in permutations (( a , b , c )): s = f ( f ( a , b ), c ) if ans == "" or len ( s ) < len ( ans ) or ( len ( s ) == len ( ans ) and s < ans ): ans = s return ans
```