arrays - 字符串数组所有排列的最长运行序列

Question

从最近对亚马逊的采访中，我发现了以下问题。我想不出一个有效的方法来解决它。
问题如下:
给定一个字符串数组，您需要在数组中字符串的所有可能排列中找到字符的最长运行序列。

输入:
ab
吧
交流电
输出:
一,3

注意:从输入输出集合来看，我觉得各个字符串的排列是做不出来的。

如果有人可以提供帮助，将不胜感激。谢谢。

Answer 1

可爱的问题。这么多角落案例。我猜这个面试问题的重点是看你提出了多少极端案例。

我希望我没有错过任何东西。

基本上有两种方法可以用字符序列来解决这个问题:

1) 是一个内部字符序列(eg. adddddddddddddddddddb)

2) 它是一个后缀、仅由该字符组成的整个字符串集合和一个前缀的连接。在这种情况下，任何字符串都不能多次使用，包括字符是同一字符串的后缀 和 前缀的情况。 (为避免生成同类字符串，后缀和前缀必须严格；即不是整个字符串)。

案例 1 很简单。我们简单地记住单个字符和序列长度，以及当前字符和序列长度。当我们读入字符串时，如果当前字符/序列长度超过最大值，我们将替换最大值。我们不必担心它与案例 2 的计算有冲突，因为它不会影响结果。

案例 2 需要更多工作。对于每个字符，我们需要保留一些数据。如果字母表很小，我们可以使用固定大小的数组，字母表中每个字符一个条目，或者我们可以使用字符哈希表。两者平均都是 O(1)；由于我们要处理的字符数不能大于所有字符串中字符的总数，因此哈希表的大小要求可以认为是O(N)。 (事实上​​，它受限于字母表的大小，所以就像固定大小的数组一样，存储要求在技术上是 O(1) 但在 Unicode 的情况下，例如，常数相当大。)

现在，我们需要什么数据？只是重复单个字符的字符串很容易；我们需要这些字符串的总长度。因此，每次我们找到这样一个字符串时，我们都可以将它的长度添加到每个字符数据中条目的总长度成员中。

对于(严格的)后缀和前缀，似乎我们只需要为每个保留一个最大长度。但是，如果我们遇到一个字符串，其前缀和后缀序列是相同的字符，并且这两个序列都比我们之前处理过的任何序列都长怎么办？我们不能将字符串同时用作后缀和前缀。幸运的是，有一个简单的答案:我们保留三个值:maximum_prefix、maximum_suffix、maximum_sum。如果我们在读取一个单词后更新表，结果发现同一个字符既是前缀又是后缀，我们更新三个值如下:

maximum_sum = max(maximum_sum, 
                  prefix_length + maximum_suffix,
                  suffix_length + maximum_prefix)
maximum_prefix = max(maximum_prefix, prefix_length)
maximum_suffix = max(maximum_suffix, suffix_length)

请注意，如果 prefix_length 或 suffix_length 为 0，上面的伪代码就可以正常工作(如果有点浪费的话)。

所以每个字符总共有四个值:homogenous_length、maximum_sum、maximum_prefix、maximum_suffix。在扫描结束时，我们需要找到 homogenous_length + maximum_sum 最大的字符；我们可以通过对字符表进行简单扫描来做到这一点。

每个字符的总处理时间为 O(1)(对于初始扫描)，即 O(N)(其中 N是问题中的字符总数，加上O(max(N, |A|))用于字符表的最后扫描(|A|是字母表的大小)；换句话说，O(N)。上面描述了空间要求。