3

Seja s uma string com todos os caracteres minúsculos.

Escreva um programa que imprima a maior substring de s em que as letras ocorram em ordem alfabética. Por exemplo:

s = 'azcbobobegghakl'

O programa deve imprimir: beggh

Em caso de haver empates, imprima a primeira substring: Por exemplo: s = 'abcbcd, o programa deve imprimir abc

Eu tentei mas não saiu nada funcional:

#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)
4
  • Tenho 95,8% de certeza que esta questão já foi respondida aqui no SOpt.
    – Woss
    Commented 15/04/2018 às 23:28
  • @Anderson Carlos Woss: eu procurei mas não achei...
    – Ed S
    Commented 15/04/2018 às 23:30
  • É, por isso que não tenho 100% de certeza, também não estou achando. Talvez ela tenha sido postada e fechada. Não sei dizer ao certo. Tentarei procurar melhor, senão qualquer coisa respondo aqui mesmo, caso ninguém tenha respondido antes.
    – Woss
    Commented 15/04/2018 às 23:32
  • @Anderson Carlos Woss: Na versão em inglês eu achei mas como não entendi o código, postei aqui!
    – Ed S
    Commented 15/04/2018 às 23:37

3 Respostas 3

4

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

2
  • Como eu visualizo as substrings usando get_all_substrings(string)? Rodei aqui e não vi nada...
    – Ed S
    Commented 16/04/2018 às 13:28
  • @EdS precisa fazer o for no resultado da função e dar o print
    – Woss
    Commented 16/04/2018 às 15:54
2

Você não estava muito longe, OP. Só precisava lembrar da maior palavra:

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

Dá pra fazer de outro modo interessante, mas um tanto "mágico" pra quem não conhece, com 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

Versão que printa comentários mostrando a evolução da função:

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'))
3
  • Poderia explicar um pouco o reduce?
    – Ed S
    Commented 16/04/2018 às 13:09
  • @EdS fica um pouco apertado de responder num comentário, por isso criei e respondi uma pergunta sobre isso. Espero que ajude! Commented 17/04/2018 às 2:19
  • ajudou muito! Obrigado!
    – Ed S
    Commented 17/04/2018 às 15:20
1

Uma modo simples de chegar ao resultado é:

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

Este aqui é o mais rápido, e no lugar de index ou slicing usa um conjunto de contadores, meu preferido:

# 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

E esta é uma solução usando recursão:

# 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

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .