shortest-string-that-contains-three-strings

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

Given three strings <code>a</code>, <code>b</code>, and <code>c</code>, 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

<ul>
	<li>A string <code>a</code> is lexicographically smaller than a string <code>b</code> (of the same length) if in the first position where <code>a</code> and <code>b</code> differ, string <code>a</code> has a letter that appears earlier in the alphabet than the corresponding letter in <code>b</code>.</li>
	<li>A substring is a contiguous sequence of characters within a string.</li>
</ul>

&nbsp;
Example 1:

<pre>
Input: a = &quot;abc&quot;, b = &quot;bca&quot;, c = &quot;aaa&quot;
Output: &quot;aaabca&quot;
Explanation: We show that &quot;aaabca&quot; 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 &quot;aaabca&quot; is the lexicographically smallest one.</pre>

Example 2:

<pre>
Input: a = &quot;ab&quot;, b = &quot;ba&quot;, c = &quot;aba&quot;
Output: &quot;aba&quot;
Explanation: We show that the string &quot;aba&quot; 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 &quot;aba&quot; is the lexicographically smallest one.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= a.length, b.length, c.length &lt;= 100</code></li>
	<li><code>a</code>, <code>b</code>, <code>c</code> consist only of lowercase English letters.</li>
</ul>

第 356 场周赛

weekly-contest-356

minimumString

高级工程师

Shortest String That Contains Three Strings

Shortest Common Supersequence 

shortest-common-supersequence

最短公共超序列

Greedy

String

Enumeration

给你三个字符串&nbsp;<code>a</code>&nbsp;，<code>b</code>&nbsp;和&nbsp;<code>c</code>&nbsp;， 你的任务是找到长度&nbsp;最短&nbsp;的字符串，且这三个字符串都是它的 子字符串&nbsp;。
如果有多个这样的字符串，请你返回 字典序最小&nbsp;的一个。

请你返回满足题目要求的字符串。

注意：

<ul>
	<li>两个长度相同的字符串 <code>a</code>&nbsp;和 <code>b</code>&nbsp;，如果在第一个不相同的字符处，<code>a</code>&nbsp;的字母在字母表中比 <code>b</code>&nbsp;的字母 靠前&nbsp;，那么字符串&nbsp;<code>a</code>&nbsp;比字符串&nbsp;<code>b</code> 字典序小&nbsp;。</li>
	<li>子字符串&nbsp;是一个字符串中一段连续的字符序列。</li>
</ul>

&nbsp;

示例 1：

<pre><code>输入：a</code> = "abc", <code>b</code> = "bca", <code>c</code> = "aaa"
输出："aaabca"
解释：字符串 "aaabca" 包含所有三个字符串：a = ans[2...4] ，b = ans[3..5] ，c = ans[0..2] 。结果字符串的长度至少为 6 ，且"aaabca" 是字典序最小的一个。</pre>

示例 2：

<pre><code>输入：a</code> = "ab", <code>b</code> = "ba", <code>c</code> = "aba"
输出："aba"
解释：字符串 "aba" 包含所有三个字符串：a = ans[0..1] ，b = ans[1..2] ，c = ans[0..2] 。由于 c 的长度为 3 ，结果字符串的长度至少为 3 。"aba" 是字典序最小的一个。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= a.length, b.length, c.length &lt;= 100</code></li>
	<li><code>a</code>&nbsp;，<code>b</code>&nbsp;，<code>c</code>&nbsp;只包含小写英文字母。</li>
</ul>