Longest Substring Without Repeating Characters

+10

Se te da una cadena s. Encuentra la subcadena más larga, una secuencia de caracteres contiguos, en la que ningún carácter aparezca dos veces, y devuelve su longitud.

Las letras mayúsculas y minúsculas cuentan como caracteres diferentes, así que a y A no son repetidos.

Función

lengthOfLongestSubstring(s: string) → integer

sstring: la cadena que se va a buscar
Devuelveinteger: la longitud de la subcadena más larga sin caracteres repetidos

Restricciones

1 ≤ s.length ≤ 5 × 10⁴
s contiene solo letras inglesas (minúsculas y mayúsculas) y dígitos.
Las letras mayúsculas y minúsculas son caracteres diferentes.

Ejemplos

Entrada: s = "coddycode"
Salida: 5
Explicación: ycode contiene cinco caracteres diferentes. Añadir d delante da como resultado dycode, con d dos veces, y ninguna otra secuencia de cinco o más caracteres evita una repetición.

Entrada: s = "racecar"
Salida: 4
Explicación: Tanto race como ecar tienen cuatro letras diferentes. Cada secuencia de cinco letras contiene la misma letra dos veces.

Entrada: s = "a1b2a3b"
Salida: 5
Explicación: Los dígitos también cuentan como caracteres, así que 1b2a3 tiene cinco caracteres distintos. Ambos tramos de seis contienen una segunda a o una segunda b.

Para ir más allá

¿Qué cambiarías si s pudiera contener cualquier carácter Unicode en lugar de letras y dígitos?

Solución

Mantén una ventana: dos bordes alrededor de una secuencia sin caracteres repetidos. El borde derecho lee cada carácter una vez y el izquierdo solo avanza, así que una pasada encuentra, para cada final, la secuencia más larga sin repeticiones que termina allí.

Comprueba cada subcadena

Correcto, pero no termina con las pruebas más grandes

Intuición

Prueba cada inicio y final, y comprueba cada subcadena añadiendo sus caracteres a un conjunto hasta que uno ya esté allí. Se comprueban todos los candidatos, así que no se puede pasar por alto la más larga válida.

Hay alrededor de n²/2 subcadenas, 1.25 × 10^9 para n = 5 × 10^4, y una comprobación puede leer hasta n caracteres: O(n³). Aquí, una comprobación se detiene después de como máximo 63 caracteres, ya que la cadena solo contiene 62 caracteres diferentes, pero aun así quedan más de mil millones de comprobaciones.

Algoritmo

Establece best en 0.
Para cada índice inicial, recorre todos los índices finales desde el inicio hasta el final de la cadena.
Añade los caracteres de la subcadena a un conjunto vacío uno por uno y detente en el primero que ya esté en el conjunto.
Si ningún carácter se repitió y la subcadena supera a best, guarda su longitud.
Devuelve best.

def lengthOfLongestSubstring(s):
    def has_no_repeat(start, end):
        seen = set()
        for k in range(start, end + 1):
            if s[k] in seen:
                return False
            seen.add(s[k])
        return True

    best = 0
    n = len(s)
    for start in range(n):
        for end in range(start, n):
            if has_no_repeat(start, end):
                best = max(best, end - start + 1)
    return best

Ventana deslizante con un conjunto

Intuición

Si abc no tiene repeticiones, comprobar abcd requiere una pregunta: ¿está d entre a, b y c? Un conjunto de los caracteres de la ventana responde de inmediato.

Mueve right un paso a la vez. Si el nuevo carácter está en el conjunto, elimina caracteres desde la izquierda hasta que desaparezca su copia anterior; después, añádelo y mide. Solo eliminas caracteres cuando es necesario, así que, para cada right, la ventana es la secuencia más larga sin repeticiones que termina ahí, y la mejor subcadena termina en algún punto. Cada carácter entra en el conjunto una vez y sale como máximo una vez: O(n).

Algoritmo

Empieza con un conjunto vacío, left = 0 y best = 0.
Mueve right por cada índice.
Mientras s[right] esté en el conjunto, elimina s[left] y avanza left un paso.
Agrega s[right] al conjunto.
Si right - left + 1 supera a best, guárdalo.
Devuelve best.

def lengthOfLongestSubstring(s):
    in_window = set()  # the characters between left and right
    left = 0
    best = 0
    for right in range(len(s)):
        # Shrink from the left until s[right] is no longer inside.
        while s[right] in in_window:
            in_window.remove(s[left])
            left += 1
        in_window.add(s[right])
        best = max(best, right - left + 1)
    return best

Ventana deslizante que salta al índice visto por última vez

Intuición

Ya sabes dónde debe situarse left: justo después de la copia anterior del nuevo carácter. Guarda el último índice de cada carácter en un mapa o en un arreglo con una posición por código de carácter, y left salta allí en un solo paso.

Salta solo cuando ese índice está en left o después. Una copia anterior ya está fuera de la ventana, y saltar hasta ella movería left hacia atrás. La ventana en cada paso es la que construye la versión con conjunto, y ahora cada carácter cuesta una consulta, una comparación y una escritura.

Algoritmo

Crea un mapa vacío que asocie cada carácter con su último índice, y establece left = 0 y best = 0.
Recorre todos los índices con right, leyendo el carácter ch que hay en ese índice.
Si la última vez que se vio ch fue en left o después, establece left en ese índice más uno.
Registra right como el último índice de ch.
Si right - left + 1 supera best, guárdalo.
Devuelve best.

def lengthOfLongestSubstring(s):
    last_seen = {}
    start = 0
    best = 0
    for i, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= start:
            start = last_seen[ch] + 1
        last_seen[ch] = i
        if i - start + 1 > best:
            best = i - start + 1
    return best

Errores comunes y casos límite

Mover left hacia atrás. En abba, la a anterior en el índice 0 ya está fuera de la ventana cuando llegas a la última a. Saltar al índice 1 vuelve a incluir la segunda b y da 3 en lugar de 2.
Contar la ventana como right - left. Ambos extremos están dentro de ella, así que suma uno.
Convertir primero la cadena a minúsculas. Aquí a y A son caracteres distintos, así que aA tiene longitud 2.
Medir solo cuando aparece una repetición. Una cadena sin repeticiones, como z, nunca la activa, y el resultado es 0.

Preguntas frecuentes3

¿Cuál es la complejidad temporal de «Subcadena más larga sin caracteres repetidos»?

La ventana deslizante se ejecuta en tiempo O(n), donde n es la longitud de la cadena: el borde derecho lee cada carácter una vez y el borde izquierdo solo avanza. El espacio adicional es O(k), donde k es el número de caracteres diferentes que puede contener la cadena; aquí, 62.

¿Deberías usar un mapa hash o un array para los últimos índices?

Ambos requieren un tiempo O(n). Con un conjunto pequeño y fijo de caracteres, como aquí, un arreglo indexado por código de carácter evita el uso de tablas hash y es más rápido.

¿Cuál es la diferencia entre una subcadena y una subsecuencia?

Una subcadena es un bloque de caracteres que están uno junto a otro, como ode en coddycode. Una subsecuencia puede omitir caracteres, como cdy. Este problema pide una subcadena, por eso funciona una ventana con dos extremos.

def lengthOfLongestSubstring(s):
    # Escribe el código aquí

Prueba #1

Prueba #2

Prueba #3

Argumento

s = "coddycode"

Salida Esperada

Longest Substring Without Repeating Characters

Función

Restricciones

Ejemplos

Pistas

Solución

Comprueba cada subcadena

Ventana deslizante con un conjunto

Ventana deslizante que salta al índice visto por última vez

Errores comunes y casos límite

Preguntas frecuentes3

Problemas similares