Wie bekomme ich den längsten alphabetisch geordneten Teilstring in Python?

Question

Ich versuche eine Funktion zu schreiben, die den längsten Teilstring von s zurückgibt, in dem die Buchstaben in alphabetischer Reihenfolge vorkommen. Zum Beispiel, wenn s = 'azcbobobegghakl', sollte die Funktion 'beggh' zurückgeben

Hier ist meine Funktion, die immer noch nicht abgeschlossen ist, aber es gibt nicht die Liste der Sub; die Rückkehr Fehler ist:

"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

Es ist nicht optimal (funktioniert in linearen ZeitO(n)), aber ich habe einige Änderungen an Ihrem Code (in 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)) 

Ausgabe:

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.

Hinweis: Wenn die Länge von zwei Sequenzen gleich ist, wird die 1. auftretende Sequenz als Ausgabe angezeigt.

Ein weiterer Eingang:

s = 'acdb' 

Ausgang:

acd 

Ich hoffe, dies wird Ihnen helfen.

Answer 2

Dies kann O (n) recht einfach:

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))