如何在 python 中获取最长的按字母顺序排列的子字符串

Question

我正在尝试编写一个函数，其中 returns 是 s 的最长子字符串，其中字母按字母顺序出现。例如，如果 s = 'azcbobobegghakl'，函数应该 return 'beggh'

这是我的函数，它还没有完成，但它没有 return 子列表； return 错误是：

"IndexError: string index out of range"

def longest_substring(s):
    sub=[]
    for i in range (len(s)-1):
        subs=s[i]
        counter=i+1
        while ord(s[i])<ord(s[counter]):
            subs+=s[counter] 
            counter+=1
        sub.append(subs)
    return sub

Answer 1

它不是最优的（在线性时间 O(n)内工作）但我对你的代码做了一些修改（在Python 3）：

def longest_substring(s):
    length = len(s)
    if length == 0 :         # Empty string
        return s
    final = s[0]
    for i in range (length-1):
        current = s[i]
        counter = i+1
        while counter < length and ord(s[i]) <= ord(s[counter]):  
            current += s[counter] 
            counter +=1
            i+=1
        if len(final) < len(current):
            final = current
    return final
s = 'azcbobobegghakl'
print(longest_substring(s))

输出：

beggh

Modifications:

You are comparing character with fixed position i.e. in while loop you are incrementing only counter not i so I incremented the ith position also.(So we avoid checking the characters which are already checked, So it does this in linear time O(n) I think..)

Also you are only checking less than for condition while ord(s[i])<ord(s[counter]): But you also have to check for equals too.

You created one list where you append every sequence which is unnecessary unless you want do any other calculations on the sequence, So I take string and if previous sequence's length is small then I updated it with new sequence.

注意：如果两个序列的长度相同，则第一个出现的序列显示为输出。

另一个输入：

s = 'acdb'

输出：

acd

希望对您有所帮助。

如何在 python 中获取最长的按字母顺序排列的子字符串

How to get longest alphabetically ordered substring in python

python-3.x

alphabetical-sort