Uma modo simples de chegar ao resultado é:
# O(len(s))
temp = sub_s = s[0]
for i in range(len(s)-1):
if s[i] <= s[i+1]:
temp += s[i+1]
if len(temp) > len(sub_s):
sub_s = temp
else:
temp = s[i+1]
print(sub_s)
Este aqui é o mais rápido, e no lugar de index ou slicing usa um conjunto de contadores, meu preferido:
# O(len(s))
prev = ' '
count = start = len_sub = ini_sub = 0
for c in s:
if c >= prev:
count += 1
else:
if count > len_sub: #se contador for maior que tamanho da sub
len_sub = count #len_sub recebe tamanho da maior sub(count)
ini_sub = start # ini_sub recebe index da maior sub(atrasado)
start += count #start guarda a index atual
count = 1
prev = c
if count > len_sub: #atualiza o ultimo loop
len_sub, ini_sub = count, start
print(s[ini_sub: len_sub + ini_sub])
#By mdgardn
E esta é uma solução usando recursão:
# O(n*n)
def longest(s, current='', sub_s=''):
if not s:
return max(sub_s, current, key=len) #se s == '' ...
else:
if not current or s[0] < current[-1]: #se current == '' ou anterior não seguir ordem alf
sub_s = max(sub_s, current, key=len) #atualiza-o com a maior sub entre os dois
current = ''
return longest(s[1:], current+s[0], sub_s) #chama a função com current ou 'herdando' a
# maior sub_s até o momento ou herdando s[0-1] para comparar com s[0]
print(longest(s))
#By kiwitrader