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

Question

给定一个字符串，找出最长的子串，其字符是连续的（即它们是连续的字母），但可能混乱（即无序）。例如：
输入："owadcbjkl"
输出："adcb"
我们认为adcb与它形成的abcd是相邻的。在

（这是一个面试问题。）

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

有没有什么方法可以在低运行时间复杂度的情况下解决这个问题？我能达到的最好结果是O（N^2），其中N是输入字符串的长度，ord()似乎是一个缓慢的操作。在

Answer 1

如果子字符串定义为''.join(sorted(substr)) in alphabet，则：

• 子字符串中没有重复项，因此 最长的子串小于（或等于）字母表的大小

• (ord(max(substr)) - ord(min(substr)) + 1) == len(substr)，其中 ord()返回字母表中的位置（+/-常量）（内置 ord()可用于小写ascii字母）

这是O(n*m*m)-时间，O(m)-空间解，其中n是{}，而{}是{}：

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

示例：

^{pr2}$