¿Por qué este código está excediendo el límite de tiempo? Subcadena más larga sin caracteres repetidos
Dado un string S, tengo que encontrar la longitud de su subcadena más larga que no tenga caracteres repetidos. Creé un código pero estaba excediendo el límite de tiempo. No pude encontrar donde. Sorprendentemente, acudí a GFG para encontrar un código similar. Aunque mi código tenía la misma lógica, incluso este código de GFG también excede el tiempo.
int longestUniqueSubsttr(string s)
{
// Creando un conjunto para almacenar las últimas posiciones
// de aparición
map<char, int> seen ;
int maximum_length = 0;
// Comenzando el punto inicial de la ventana en el índice 0
int start = 0;
for(int end = 0; end < s.length(); end++)
{
// Verificando si ya hemos visto el elemento o no
if (seen.find(s[end]) != seen.end())
{
// Si hemos visto el número, movemos el puntero de inicio
// a la posición después de la última aparición
start = max(start, seen[s[end]] + 1);
}
// Actualizando el último valor visto del carácter
seen[s[end]] = end;
maximum_length = max(maximum_length,
end - start + 1);
}
return maximum_length;
“`
input: geeksforgeeks
output: 7 (eksforg)
¿Alguien sabe por qué está sucediendo eso?
davy.ai
Como modelo de lenguaje de IA, no tengo acceso a los entornos donde se ejecuta el código. Sin embargo, parece que el código está utilizando un mapa para realizar un seguimiento de las últimas posiciones de ocurrencia para cada carácter. Esta operación tiene una complejidad de tiempo promedio de O(log n), donde n es el tamaño del mapa. En el peor escenario, el mapa puede llegar a ser tan grande como el tamaño de la cadena de entrada, lo que resulta en una complejidad de tiempo de O(n log n). Podría ser posible optimizar el algoritmo utilizando una estructura de datos diferente o mejorando la lógica. Alternativamente, el tamaño de entrada podría ser demasiado grande para que el algoritmo pueda manejarlo dentro del límite de tiempo.