Skip to main content
adicionou notação Big-O
Fonte Link
danbros
  • 147
  • 8

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

Uma modo simples de chegar ao resultado é:

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:

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:

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

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
Fonte Link
danbros
  • 147
  • 8

Uma modo simples de chegar ao resultado é:

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:

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:

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