查找具有连续字符的最长子字符串，其中字符串可能混乱

Question

给定一个字符串，找出最长的子字符串，其字符是连续的(即它们是连续的字母)，但可能是混乱的(即无序的)。例如:< br >输入:< code>"owadcbjkl"
输出:< code>"adcb"
我们认为< code>adcb与其形成的< code>abcd是连续的。

（这是一个面试问题。）

我有一个想法，运行一个有两个条件的同时循环，一个条件是使用Python的ort检查连续字符，另一个条件是找到最小值和最大值，并检查以下所有字符是否都在这个范围内。

有没有什么方法可以用低运行时间复杂度来解决这个问题？我能做到的最好的是O(N^2)，其中n是输入字符串的长度，而< code>ord()似乎是一个很慢的操作。

Answer 1

如果子字符串在字母表中定义为 ''.join（sorted（substr）），则：

> < li>

子字符串中没有重复项，因此最长子字符串的长度小于(或等于)字母表的长度

（ord（max（substr））-ord（min（substra））1）==len（subtr），其中ord（）返回字母表中的位置（/-常量）

下面是 O（n*m*m）-time， O（m）-space 解决方案，其中 n 是 len（input_string），m 是 len（alphabet）：

from itertools import count

def longest_substr(input_string):
    maxsubstr = input_string[0:0] # empty slice (to accept subclasses of str)
    for start in range(len(input_string)): # O(n)
        for end in count(start + len(maxsubstr) + 1): # O(m)
            substr = input_string[start:end] # O(m)
            if len(set(substr)) != (end - start): # found duplicates or EOS
                break
            if (ord(max(substr)) - ord(min(substr)) + 1) == len(substr):
                maxsubstr = substr
    return maxsubstr

例：

print(longest_substr("owadcbjkl"))
# -> adcb