A ideia pode ser bem mais simples do que parece e, aliás, essa é uma questão que foi proposta em uma entrevista de emprego em alguma empresa grande do ramo, não lembro direito se Google ou Facebook (ou ainda outra não relacionada com essas).Você consegue gerar todas as substrings necessárias analisando a string do primeiro caractere até o final, depois do segundo caractere até o final, depois do terceiro, assim por diante. Esta forma não gera todas as substrings possíveis, mas todas as que precisam ser analisadas. Uma função para isso poderia ser:
def get_all_substrings(string):
for index in range(len(string)):
yield string[index:]
Ela retornará um gerador (iterador) que representará a seguinte sequência de strings:
azcbobobegghakl
zcbobobegghakl
cbobobegghakl
bobobegghakl
obobegghakl
bobegghakl
obegghakl
begghakl
egghakl
gghakl
ghakl
hakl
akl
kl
l
Assim, analisando uma a uma, você pode obter a maior sequência de caracteres em ordem crescente, contando a partir do início. Neste caso, a função poderia ser:
def get_bigest_substring(string):
for index, characters in enumerate(zip(string, string[1:])):
a, b = characters
if b < a:
return string[:index+1]
return string
Assim, o retorno da função para cada substring seria, representando a maior sequência de caracteres em ordem crescente:
az
z
c
bo
o
bo
o
beggh
eggh
ggh
gh
h
akl
kl
l
E, por fim, bastaria verificar qual sequência possui o maior comprimento. Para tal, pode utilizar a função nativa max
. O código final ficaria:
def get_all_substrings(string):
for index in range(len(string)):
yield string[index:]
def get_bigest_substring(string):
for index, characters in enumerate(zip(string, string[1:])):
a, b = characters
if b < a:
return string[:index+1]
return string
substrings = (get_bigest_substring(string)
for string in get_all_substrings('azcbobobegghakl'))
bigest_substring = max(substrings, key=len)
print(bigest_substring)
Veja funcionando no Ideone | Repl.it