The idea may be a lot simpler than it looks and, incidentally, this is an issue that was proposed in a job interview at some big business in the business, I do not remember right if Google or Facebook (or another not related to you can generate all the required substrings by parsing the string of the first character to the end, after the second character to the end, after the third character, and so on. This form does not generate all possible substrings , but all that need to be parsed. One function for this could be:
def get_all_substrings(string):
for index in range(len(string)):
yield string[index:]
It will return a generator (iterator) that will represent the following sequence of strings :
azcbobobegghakl
zcbobobegghakl
cbobobegghakl
bobobegghakl
obobegghakl
bobegghakl
obegghakl
begghakl
egghakl
gghakl
ghakl
hakl
akl
kl
l
So by analyzing one by one, you can get the largest string in ascending order by counting from the beginning. In this case, the function could be:
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
So, the function return for each substring would be, representing the largest sequence of characters in ascending order:
az
z
c
bo
o
bo
o
beggh
eggh
ggh
gh
h
akl
kl
l
And finally, it would suffice to check which sequence has the longest length. To do this, you can use the native max
function. The final code would look like this:
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)
See working at Ideone | Repl.it