如果子字符串定义为''.join(sorted(substr)) in alphabet
then:
子字符串中没有重复项,因此最长子字符串的大小小于(或等于)字母表的大小
(ord(max(substr)) - ord(min(substr)) + 1) == len(substr)
, 其中
ord()
返回字母表中的位置(+/- 常量)(内置
ord()
可用于小写 ascii 字母)
这是O(n*m*m)
-time, O(m)
-space 解决方案,其中n
islen(input_string)
和m
is 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