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

2

Let s be a string with all lowercase characters.

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

s = 'azcbobobegghakl'

The program should print: beggh

If there are ties, print the first substring: For example: s = 'abcbcd, the program should 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)
    
asked by anonymous 16.04.2018 / 00:29

2 answers

2

You were not too far away, OP. All you had to do was 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

It makes it interesting, but somewhat "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 printers 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'))
    
16.04.2018 / 02:45
3

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

    
16.04.2018 / 03:24