#2800

Shortest String That Contains Three Strings

expert · 1150 · lc medium +32 · verified · 31.6% accepted · 372 likes · top 9%

Description

Three strings a, b, and c are given. Find the shortest string that contains all three as substrings. Among all shortest solutions, return the lexicographically smallest one.

Notes

- String a is lexicographically smaller than b (of the same length) if at the first differing position, a's character comes earlier in the alphabet.

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

Code

1

2

3

class Solution:
    def minimumString(self, a: str, b: str, c: str) -> str:

class Solution:
    def minimumString(self, a: str, b: str, c: str) -> str: