Python - AYUDA! Problema con la memoria constante

 
Vista:

AYUDA! Problema con la memoria constante

Publicado por Lucho (1 intervención) el 28/05/2019 19:01:39
Buenas tardes para todos, resulta que estoy aplicando en un nuevo trabajo y me enviaron este ejercicio:

-----------
Write a function which given a string, finds the length of the longest substring without repeating characters.

For example:
In: "abcabcbb"
Out: 3
Why: The answer is "abc", with the length 3.

In: "bbbbb"
Out: 1
Why: The answer is "b", with length 1.

---------

A lo que mi solución fue la siguiente:

1
2
3
4
5
6
7
8
9
def longest_substring(s: str) -> int:
    n = len(s) - 1
    while n > 0:
        groups = [s[i:i+n] for i in range(0, len(s), n)]
        for g in groups:
            if len(g) == n:
                if len(set(g)) == len(g):
                    return len(g)
        n -= 1


Pero me observaron lo siguiente y no se como resolverlo:

"tiene un error de uno por uno, pero no es nada.
Los requisitos de memoria son exponenciales a la longitud de la cadena!.
Finalmente, el espacio de búsqueda se considera completamente N veces para una entrada de tamaño N, tiene O (n²).
Por favor, resuelva el problema en O (n) y en la memoria constante."

Les pido por favor si pueden ayudarme ya que no logro solucionarlo!!!

Muchas gracias de antemano a todos!
Valora esta pregunta
Me gusta: Está pregunta es útil y esta claraNo me gusta: Está pregunta no esta clara o no es útil
0
Responder