アルファベット順に最長のアルファベット順の部分文字列を取得するには

Question

文字のアルファベット順の最長部分文字列を返す関数を記述しようとしています。たとえば、s = 'azcbobobegghakl'の場合、関数は 'beggh'を返します。

これは私の関数ですが、まだ完全ではありませんが、サブのリストは返されません。

"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.

注： 2つの配列の長さが同じ場合は、最初に出現した配列が出力として表示されます。

別の入力：

s = 'acdb' 

出力：

acd 

私は、これはあなたを助けることを願っています。

Answer 2

これはかなり単純O（n）を行うことができる。

def gen(s): 
    prev = '' 
    for c in s: 
     if c >= prev[-1:]: 
      prev += c 
     else: 
      yield prev 
      prev = c 
    if prev: 
     yield prev 

print(max(gen('azcbobobegghakl'), key=len))