Shortest String Holding Three Words

Medium

You are given three strings first, second and third. Build the shortest string that contains each of them as a substring (a contiguous piece). If several strings of that minimal length exist, return the one that comes first alphabetically (the lexicographically smallest). The pieces may overlap: "cat" and "tea" fit into "catea", and a string that already sits entirely inside another one needs no extra room.

Example 1

first="cat", second="tea", third="eat" → 'cateat'

"cat" and "tea" share the letter t, giving "catea"; appending t gives "cateat", which also contains "eat". Nothing shorter than 6 letters works.

Example 2

first="ab", second="b", third="ba" → 'aba'

"aba" contains all three strings, and two letters cannot hold both "ab" and "ba".

Example 3

first="z", second="y", third="x" → 'xyz'

No letters overlap, so any arrangement of the three letters has length 3; the alphabetically smallest is "xyz".

Constraints

1 ≤ len(first), len(second), len(third) ≤ 100
The strings consist of lowercase English letters only

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy String Enumeration

Similar problems

Erase Digits Until It Divides by 25 Medium Pattern Woven Several Times Hard Strike Out a Digit for the Maximum Easy Biggest Number From Pieces Medium Every Letter Once Medium

Input

first="cat", second="tea", third="eat"

Expected

'cateat'

Run checks the first 3 tests in your browser. Submit checks all 114 tests on the server, hidden ones included.