Print the largest substring of s where the letters occur in alphabetical order

Question

Be a string with all lowercase characters.

Write a program that prints the largest substring of s in which the letters occur in alphabetical order. For example:

s = 'azcbobobegghakl'

The program must print: beggh

In case of ties, print the first substring: For example: s = 'abcbcd, the program must print abc

I tried but nothing functional came out:

#s = 'azcbobobegghakl'
s = "abcdeka"
indice =0
palavra = ""
resposta = ""

while indice < len(s)-1:
    if s[indice] <=s[indice +1] :
        palavra += s[indice]
        indice +=1
    indice +=1
print(palavra)

Answer 1

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}

Answer 2

You weren’t far away, OP. I just needed to remember the biggest word:

s = "azcbobobegghakl"
indice = 0
palavra = ""
resposta = ""

maior_palavra = ""
while indice < len(s) - 1:

    if palavra == "":
        palavra = s[indice]
        if len(palavra) > len(maior_palavra):
            maior_palavra = palavra

    if s[indice] <= s[indice + 1]:
        palavra += s[indice + 1]
        if len(palavra) > len(maior_palavra):
            maior_palavra = palavra

    else:
        palavra = ''
    indice += 1

print(maior_palavra)  # beggh

---

You can do otherwise interesting, but rather "magical" for those who do not know, with reduce:

from functools import reduce

def achar_maior_sequencia(s):

    maior_sequencia = ''

    def achar_sequencia(sequencia_atual: str, proximo: str):
        nonlocal maior_sequencia

        # Se não for alfanumérico, quebrar a sequencia
        if not proximo.isalnum():
            if len(sequencia_atual) > len(maior_sequencia):
                maior_sequencia = sequencia_atual
            return ''

        # Se não houver sequência, a sequência passa a ser o único caracter
        if sequencia_atual == '':
            return proximo

        # Se a última letra da sequência atual for menor ou igual do que
        # a próxima letra, adicionamos a letra à sequencia atual
        if sequencia_atual[-1] <= proximo:
            if len(sequencia_atual) > len(maior_sequencia):
                maior_sequencia = sequencia_atual
            return sequencia_atual + proximo

        if len(sequencia_atual) > len(maior_sequencia):
            maior_sequencia = sequencia_atual

        return proximo

    reduce(achar_sequencia, s)
    return maior_sequencia

print(achar_maior_sequencia('azcbobobegghakl'))  # beggh

Version that prints comments showing the evolution of the function:

from functools import reduce

maior_sequencia = ''
def achar_sequencia(sequencia_atual: str, proximo: str):

    print('Sequência atual: {}\tPróximo: {}\tResultado: {}'.format(sequencia_atual, proximo, sequencia_atual + proximo))

    # Se não for alfanumérico, quebrar a sequencia
    if not proximo.isalnum():
        print('Não é alfanumérico, quebrar sequência atual.')
        return ''

    # Se não houver sequência, a sequência passa a ser o único caracter
    if sequencia_atual == '':
        print('Primeiro caractere da sequência atual.')
        return proximo

    # Se a última letra da sequência atual for menor ou igual do que
    # a próxima letra, adicionamos a letra à sequencia atual
    if sequencia_atual[-1] <= proximo:
        print('Ordem é alfabética, adicionar próximo a sequência atual')
        # print(sequencia_atual + proximo)
        return sequencia_atual + proximo

    print('Ordem alfabética quebrada, reiniciar sequência com próximo como primeiro caractere')
    return proximo

print(reduce(achar_sequencia, 'azcbobobegghakl'))

from functools import reduce

def achar_maior_sequencia(s):

    maior_sequencia = ''

    def achar_sequencia(sequencia_atual: str, proximo: str):
        nonlocal maior_sequencia

        print('Sequência atual: {}\tPróximo: {}\tResultado: {}'.format(sequencia_atual, proximo,
                                                                       sequencia_atual + proximo))
        # Se não for alfanumérico, quebrar a sequencia
        if not proximo.isalnum():
            print('Não é alfanumérico, quebrar sequência atual.')
            return ''

        # Se não houver sequência, a sequência passa a ser o único caracter
        if sequencia_atual == '':
            print('Primeiro caractere da sequência atual.')
            return proximo

        # Se a última letra da sequência atual for menor ou igual do que
        # a próxima letra, adicionamos a letra à sequencia atual
        if sequencia_atual[-1] <= proximo:
            print('Ordem é alfabética, adicionar próximo a sequência atual')
            if len(sequencia_atual) > len(maior_sequencia):
                maior_sequencia = sequencia_atual
            return sequencia_atual + proximo

        # Se a função chegar aqui, é porque não retornamos logo acima e a ordem não é mais alfabética
        print('Ordem alfabética quebrada, reiniciar sequência com próximo como primeiro caractere')

        if len(sequencia_atual) > len(maior_sequencia):
            maior_sequencia = sequencia_atual

        return proximo

    reduce(achar_sequencia, s)
    return maior_sequencia

print(achar_maior_sequencia('azcbobobegghakl'))

Answer 3

A simple way to get the result is:

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

This one is the fastest, and instead of index or slicing uses a set of counters, my favorite:

# 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

And this is a solution using recursion:

# 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