The idea may be much simpler than it seems and, incidentally, this is an issue that was proposed in a job interview in some large company in the industry, I can not remember right if Google or Facebook (or yet another unrelated to these). You can generate all substrings necessary by analyzing the string from the first character to the end, from the second character to the end, from the third character, so on. This form does not generate all substrings possible, but all that need to be analyzed. A 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 longest string in ascending order, 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
Thus, the return of the function for each substring would represent 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 be enough to check which sequence has the longest length. To do this, you can use the native function max
. The final code would be:
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 on Ideone | Repl.it
I am 95.8% sure that this question has already been answered here at Sopt.
– Woss
@Anderson Carlos Woss: I searched but did not find...
– Ed S
Yeah, that’s why I’m not 100% sure, I’m not sure either. Maybe it was posted and closed. I can’t say for sure. I’ll try to look harder, or else I’ll answer right here, in case no one has answered before.
– Woss
@Anderson Carlos Woss: In the English version I found but as I didn’t understand the code, posted here!
– Ed S