python - 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 次，所以我们可以说在最坏的情况下代码将运行

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

那么 O(N) 是可以接受的吗？

现在问题是

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

Answer 1

1. 是 O(N)
2. 'why to use DP of O(N2)' : 这个问题你不需要。但是请注意，您利用了序列标记(字母)是有限的这一事实 - 因此您可以设置一个列表来保存所有可能的起始值 (26)，并且您只需要查找该列表中最长的成员- O(1) 操作。更多generalised solution对于具有任意数量的有序标记的序列，可以在 O(NlogN) 中完成。

3. 您 friend 的代码基本相同，只是将字母映射到数字，他们的 26 个起始位置列表包含 26 个数字用于字母计数 - 他们不需要执行任何一个操作。不过，从概念上讲，它是同一件事——持有一个列表列表。

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

   您可能会注意到“获胜”序列是平局的细微差别。例如 - 在您拥有的测试字符串 edxeducation 上 - 您的实现返回 ddin 而您 friend 的返回 ddio。两者对我来说似乎都有效 - 没有打破这种联系的规则。

4. 此代码的主要限制是它只能在一种特定情况下处理完全由字母组成的序列。您可以扩展它以处理大写和小写字母，或者将它们相同对待，或者使用所有小写字母“小于”所有大写字母或类似的顺序。这只是扩展了它可以处理的有限 token 集。

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