O(N) 中的最长递增子序列代码？

Question

有人问我问题

Find the longest alphabetically increasing or equal string 
composed of those letters. Note that you are allowed to drop 
unused characters.

So ghaaawxyzijbbbklccc returns aaabbbccc.

Is an O(n) solution possible?

我在 python]

中实现了它的代码

s = 'ghaaawxyzijbbbklccc'
lst = [[] for i in range(26)]

for ch in s:
    ml = 0
    for i in range(0,ord(ch) + 1 - ord('a')):
        if len(lst[i]) > len(lst[ml]):
            ml= i
    cpy = ''.join(lst[ml])
    lst[ord(ch) - ord('a')] = cpy + ch

ml = 0
for i in range(26):
    if len(lst[i]) > len(lst[ml]):
        ml = i
print lst[ml]

答案是'aaabbbccc'

我已经尝试了更多的例子，一切正常！据我所知，这段代码的复杂度是 O(N) 让我们举个例子假设我有一个字符串 'zzzz' 所以主循环将运行 4 次，内部循环每次迭代将运行 26 次所以我们可以说在最坏的情况下代码将运行 in

O(26*N + 26)
---------^-
this is the last iteration

所以 O(N) 是可以接受的？

现在问题是

它在 O(N) 中有效吗 my code at ideone
如果它在 O(N) 中工作那么为什么要使用 O(N2) 的 DP code of DP
比这个代码好吗Friends code
此代码的限制

Answer 1

这是 Longest Increasing Subsequence 的变体。区别在于您的元素是有界的，因为它们只能从 'a' 到 'z' 运行。你的算法确实是 O(N)。 O(N log N) 是可能的，例如使用上面 link 中的算法。可能元素数量的限制将其转化为 O(N)。

Answer 2

是 O(N)
'why to use DP of O(N2)' ：这个问题你不需要。但是请注意，您利用了序列标记（字母）是有限的这一事实 - 因此您可以设置一个列表来保存所有可能的起始值 (26)，并且您只需要查找该列表中最长的成员- O(1) 操作。对于具有任意数量的有序标记的序列，可以在 O(NlogN) 中完成 generalised solution。
你朋友的代码基本上是一样的，只是将字母映射到数字，他们的 26 个起始位置列表包含 26 个字母数 - 他们不需要做任何一个。不过，从概念上讲，它是同一件事——持有一个列表列表。

"Better"见仁见智。虽然它具有相同的渐近复杂度，但常数项可能不同，因此一个可能比另一个执行得更快。此外，就存储而言，一个可能比另一个使用的内存略多。如此低 n - 判断哪个更具可读性可能比任一算法的绝对性能更重要。我不打算做出判断。

您可能会注意到 "winning" 序列是平局的细微差别。例如 - 在你的测试字符串 edxeducation 上 - 你的实现 returns ddin 而你朋友的 returns ddio。两者对我来说似乎都有效 - 没有打破这种联系的规则。
此代码的主要限制是它只能在一种特定情况下处理完全由字母组成的序列。您可以扩展它以处理大写和小写字母，或者对它们进行相同处理，或者使用所有小写字母 "less than" 所有大写字母或类似的顺序。这只是扩展了它可以处理的有限令牌集。

概括此限制 - 代码将仅处理上面 2. 中所述的有限序列标记集。此外 - 没有错误处理，因此如果您输入带有数字或标点符号的字符串，它将失败。

O(N) 中的最长递增子序列代码？

Longest Increasing Subsequence code in O(N)?

python

algorithm

time-complexity

longest-substring