Problem

Given three strings a, b, and c, your task is to find a string that has theminimum 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.

Examples

Example 1

1
2
3

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

1
2
3

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.

Solution

Method 1 – Greedy Overlap and Permutations

Intuition

Try all 6 permutations of the three strings. For each, greedily overlap as much as possible when concatenating. Track the shortest and lex smallest result.

Approach

  1. For each permutation of (a, b, c):
    • Merge the first two strings with maximal overlap.
    • Merge the result with the third string with maximal overlap.
  2. Track the shortest and lex smallest merged string containing all three as substrings.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

from itertools import permutations
class Solution:
    def minimumString(self, a, b, c):
        def merge(x, y):
            for l in range(min(len(x), len(y)), 0, -1):
                if x[-l:] == y[:l]:
                    return x + y[l:]
            return x + y
        best = None
        for p in permutations([a, b, c]):
            s = merge(merge(p[0], p[1]), p[2])
            if all(x in s for x in [a, b, c]):
                if best is None or len(s) < len(best) or (len(s) == len(best) and s < best):
                    best = s
        return best
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

import java.util.*;
class Solution {
    private String merge(String x, String y) {
        for (int l = Math.min(x.length(), y.length()); l > 0; --l)
            if (x.substring(x.length()-l).equals(y.substring(0, l)))
                return x + y.substring(l);
        return x + y;
    }
    public String minimumString(String a, String b, String c) {
        String[] arr = {a, b, c};
        String best = null;
        for (int i = 0; i < 3; ++i) for (int j = 0; j < 3; ++j) for (int k = 0; k < 3; ++k) {
            if (i == j || j == k || i == k) continue;
            String s = merge(merge(arr[i], arr[j]), arr[k]);
            if (s.contains(a) && s.contains(b) && s.contains(c)) {
                if (best == null || s.length() < best.length() || (s.length() == best.length() && s.compareTo(best) < 0))
                    best = s;
            }
        }
        return best;
    }
}

Complexity

  • ⏰ Time complexity: O(L^2) for each merge, 6 permutations, L = max string length (up to 100).
  • 🧺 Space complexity: O(L) for the result string.