What is the pattern used in the shortest string containing three strings problem?

The problem follows a greedy choice pattern where string overlaps are maximized while maintaining an invariant that all strings are present as substrings.

How do I ensure the shortest string is also lexicographically smallest?

You need to check all possible combinations of string orders and validate that the resultant string is the shortest and lexicographically smallest.

Can I solve the problem without using enumeration of string combinations?

No, enumeration of all combinations is necessary to ensure the shortest valid string is found, especially when considering lexicographical order.

What is a common mistake when implementing the greedy approach for this problem?

A common mistake is failing to correctly overlap the strings, which results in unnecessarily long strings that do not satisfy the problem requirements.

What does invariant validation mean in this context?

Invariant validation ensures that all three input strings are present as substrings in the final string. If any string is missing, the current combination is invalid.

#2800

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

包含三个字符串的最短字符串

给你三个字符串 a ， b 和 c ，你的任务是找到长度最短的字符串，且这三个字符串都是它的子字符串。如果有多个这样的字符串，请你返回字典序最小的一个。请你返回满足题目要求的字符串。注意：两个长度相同的字符串 a 和 b ，如果在第一个不相同的字符处， a 的字母在字母表中比 …

字符串贪心枚举

题目描述

给你三个字符串 a ，b 和 c ，你的任务是找到长度最短的字符串，且这三个字符串都是它的 子字符串 。

如果有多个这样的字符串，请你返回 字典序最小 的一个。

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

注意：

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

示例 1：

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

示例 2：

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

提示：

1 <= a.length, b.length, c.length <= 100
a ，b ，c 只包含小写英文字母。

lightbulb

解题思路

方法一：枚举

我们枚举三个字符串的所有排列，然后对于每个排列，对三个字符串进行合并，找到最短的且字典序最小的字符串。

时间复杂度 $O(n^2)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是三个字符串的长度的最大值。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

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

speed

复杂度分析

指标	值
时间	complexity depends on the approach used for finding overlaps and enumerating combinations. Space complexity varies with the number of string combinations stored and processed during the calculation of overlaps.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate demonstrates an understanding of greedy string matching and overlap techniques.
question_mark
The candidate efficiently handles different combinations of string overlaps to minimize the final string length.
question_mark
The candidate ensures that the lexicographical order is maintained in case of multiple valid results.

warning

常见陷阱

外企场景

error
Failing to check all possible combinations of string orders, leading to missing the lexicographically smallest result.
error
Not handling string overlaps correctly, resulting in unnecessarily long strings.
error
Not validating the invariant at each step, potentially leading to invalid results.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to work with more than three strings and find the shortest string containing all of them.
arrow_right_alt
Implement a solution where string overlaps are not allowed and each string must be added fully to the result.
arrow_right_alt
Change the problem to return the longest valid string instead of the shortest one while still containing all substrings.

help

常见问题

外企场景

继续练习

#2844 生成特殊数字的最少操作 #2259 移除指定数字得到的最大结果 #2014 重复 K 次的最长子序列