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:
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!
-----------
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
0