Minimum Window Substring
Recibes dos cadenas, s y t. Encuentra la subcadena más corta de s, un tramo de caracteres consecutivos, que contenga todos los caracteres de t, contando las repeticiones: si t contiene una letra dos veces, la subcadena debe contenerla al menos dos veces. El orden no importa y la subcadena también puede contener otros caracteres.
Si varias subcadenas tienen la misma longitud mínima, devuelve la que aparece más a la izquierda. Si ninguna subcadena de s contiene todos los caracteres de t, devuelve una cadena vacía.
Función
- sstring
- la cadena en la que buscar
- tstring
- los caracteres que debe contener la ventana, incluidas las repeticiones
- Devuelvestring
- la subcadena más corta y, después, la más a la izquierda de s que contiene todo t, o una cadena vacía
Restricciones
1 ≤ s.length ≤ 5 × 1041 ≤ t.length ≤ 104sytcontienen solo letras inglesas. Las letras mayúsculas y minúsculas son caracteres diferentes.- Cuando varias subcadenas son las más cortas, la respuesta es la que aparece más a la izquierda; cuando no existe ninguna, es
"".
Ejemplos
- Entrada
- s = "mappingtheplan"t = "nap"
- Salida
- "plan"
- Explicación
- Al leer de izquierda a derecha, la primera ventana que contiene una
n, unaay unapesappin, de cinco caracteres.plan, al final, contiene las tres en cuatro caracteres, y ningún tramo de tres caracteres las contiene.
- Entrada
- s = "banana"t = "aan"
- Salida
- "ana"
- Explicación
tpide dos copias deay una den.anaen el índice 1 contiene exactamente eso. Una segundaanaempieza en el índice 3, y gana la que está más a la izquierda.
- Entrada
- s = "Coddy"t = "cd"
- Salida
- ""
- Explicación
- La única C en
Coddyestá en mayúscula, y las letras mayúsculas y minúsculas son caracteres diferentes. Ninguna subcadena contiene unacminúscula, así que la respuesta es la cadena vacía.
+17 pruebas ocultas al enviar
Para ir más allá
Cuando t usa solo unas pocas letras y s es larga, la mayor parte de s nunca puede importar. ¿Puedes hacer que la ventana salte solo entre las posiciones que contienen una letra de t?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Una ventana que contiene todo
tsigue conteniéndolo cuando la haces más larga, y una ventana a la que le falta algo sigue sin contenerlo cuando la haces más corta. Aprovecha eso para evitar probar cada inicio con cada final.Avanza un borde derecho hasta que la ventana cubra
t. Después, avanza el borde izquierdo mientras la ventana siga cubriendot, registrándolo cada vez. Ningún borde tiene que retroceder.Lleva una tabla de cuántas copias más de cada carácter necesita la ventana y un número,
missing, que indique cuántas copias le faltan en total. Un carácter que entra reducemissingsolo si todavía hacía falta, y un carácter que sale lo aumenta solo si la ventana se queda corta de ese carácter. La ventana contienetexactamente cuandomissinges 0.
Solución
La respuesta depende de cuántos caracteres de cada tipo contiene una ventana, no de su orden, y la mejor ventana puede empezar en cualquier lugar. Probar cada inicio con cada final implica O(n²) ventanas. La clave es una ventana cuyos extremos solo avanzan: el extremo derecho la amplía hasta que cubre t, el izquierdo la reduce mientras siga cubriéndolo, y un contador de caracteres faltantes te indica en un solo paso si cubre t.
Amplía una ventana desde cada inicio
Correcto, pero no termina con las pruebas más grandes
Intuición
Fija dónde empieza la subcadena. Luego hazla crecer de un carácter en un carácter, llevando la cuenta de cada carácter que contiene, y después de cada paso comprueba si cubre t: para cada una de las u letras distintas que usa t, la ventana debe contener al menos tantas copias como t. El primer extremo que cumple esta condición da la ventana de cobertura más corta para este inicio, porque primero se comprobó cada una de las más cortas con el mismo inicio y ninguna cumplió la condición. Detente ahí.
Hazlo para cada inicio y conserva la ventana más corta. Los inicios se prueban de izquierda a derecha y una ventana reemplaza a la mejor solo cuando es estrictamente más corta, así que, entre las ventanas de la misma longitud, se mantiene la que está más a la izquierda.
Es lento cuando las ventanas son largas o no se encuentran. Si la única Z de s está justo al final y t pide una, cada inicio recorre todo el camino hasta el final: alrededor de n²/2 pasos, que son 1.25 × 10^9 para n = 5 × 10^4, cada uno con una comprobación de hasta 52 letras. Lo mismo ocurre cuando no existe ninguna ventana.
Algoritmo
- Cuenta cuántas copias de cada carácter pide
ty enumera las letras que utiliza. - Para cada
start, borra una tabla de conteos y mueveenddesdestarthasta el final des, añadiendos[end]a la tabla. - Después de cada adición, comprueba cada letra de
t. Si la ventana contiene suficientes copias de cada una, compara su longitud con la mejor hasta el momento, consérvala si es estrictamente más corta y deja de ampliarla. - Después de todos los inicios, devuelve la mejor ventana o
""si ninguna cubriót.
def minWindow(s, t):
need = [0] * 128 # copies of each character code that t asks for
for ch in t:
need[ord(ch)] += 1
letters = [c for c in range(128) if need[c] > 0]
best_start, best_len = 0, len(s) + 1
for start in range(len(s)):
have = [0] * 128 # counts inside s[start..end]
for end in range(start, len(s)):
have[ord(s[end])] += 1
if all(have[c] >= need[c] for c in letters):
# The first end that covers t gives the shortest window from this start.
if end - start + 1 < best_len:
best_start, best_len = start, end - start + 1
break
if best_len > len(s):
return ""
return s[best_start:best_start + best_len]Ventana deslizante que comprueba cada letra
Intuición
Dos hechos eliminan la necesidad de reiniciar. Añadir caracteres a una ventana que cubre t hace que siga cubriéndolo, y quitar caracteres de una ventana a la que le falta algo hace que siga faltándole. Así que, cuando el inicio se mueve a la derecha, el final de la ventana de cobertura más corta solo puede quedarse donde está o moverse a la derecha. Ambos extremos pueden avanzar juntos y ninguno retrocede.
Mueve right por s, añadiendo cada carácter a una tabla de recuentos. Siempre que la ventana cubra t, es una candidata: regístrala si es más corta que la mejor, luego quita s[left] y avanza left, y vuelve a comprobarlo. Repite hasta que la ventana deje de cubrir t; después, vuelve a ampliarla por la derecha.
No se pasa por alto ninguna ventana. Toma la mejor ventana, desde L hasta R. Si left hubiera superado L antes de que right llegara a R, alguna ventana desde L que terminara antes de R habría cubierto t, y sería más corta que la mejor. Así que, cuando right llega a R, el bucle de reducción avanza left hasta L y registra la mejor ventana. Cada extremo se mueve como máximo n veces, pero cada comprobación lee hasta u recuentos, uno por cada letra que usa t, aunque solo haya cambiado un recuento desde la última comprobación.
Algoritmo
- Cuenta las copias que requiere
ty enumera sus letras; empieza con una ventana vacía,left = 0, y una longitud mínima den+1. - Avanza
rightpor todos los índices y añades[right]a los recuentos de la ventana. - Mientras la ventana contenga suficientes copias de cada letra de
t, registra la ventana si es estrictamente más corta que la mejor, eliminas[left]de los recuentos y avanzaleft. - Devuelve la mejor ventana, o
""si la mejor longitud sigue siendon+1.
def minWindow(s, t):
need = [0] * 128 # copies of each character code that t asks for
for ch in t:
need[ord(ch)] += 1
letters = [c for c in range(128) if need[c] > 0]
have = [0] * 128 # counts inside s[left..right]
def covers():
for c in letters:
if have[c] < need[c]:
return False
return True
left = 0
best_start, best_len = 0, len(s) + 1
for right in range(len(s)):
have[ord(s[right])] += 1 # expand on the right
while covers(): # shrink from the left while the window still covers t
if right - left + 1 < best_len:
best_start, best_len = left, right - left + 1
have[ord(s[left])] -= 1
left += 1
if best_len > len(s):
return ""
return s[best_start:best_start + best_len]Ventana deslizante con un contador faltante
Intuición
Mantén la misma ventana y reemplaza la comprobación por un número. Sea need[c] la cantidad de copias de c que requiere t menos las copias que hay dentro de la ventana. Un valor positivo significa que aún faltan algunas en la ventana; uno negativo, que tiene copias de sobra. Sea missing el número total de copias que faltan en la ventana, que comienza siendo la longitud de t. La ventana contiene exactamente t cuando missing es 0.
Actualizarlo cuesta un paso. Cuando s[right] entra y su valor de need es mayor que 0, llena un hueco, así que missing disminuye en uno; en cualquier caso, need disminuye en uno y puede pasar a ser negativo si hay una copia de sobra. Cuando s[left] sale, need aumenta en uno y, si ahora es mayor que 0, la ventana cedió una copia que t necesitaba, así que missing aumenta en uno. Las copias de sobra aparecen y desaparecen sin afectar a missing.
Traza s = banana, t = aan: al principio, need tiene a 2, n 1 y missing vale 3. b no se necesita. La primera a hace que missing pase a 2; la n, a 1; la segunda a, a 0, así que bana contiene t. Al reducir la ventana, se descarta la copia de sobra b y queda ana, de tres caracteres, que pasa a ser la mejor. Al descartar esa a, missing vuelve a 1. La última a vuelve a cubrir t con nana, que se reduce hasta la segunda ana. No es más corta, así que se conserva la ana más a la izquierda.
Cada carácter de s entra en la ventana una vez y sale como máximo una vez, y cada movimiento cuesta una cantidad fija de trabajo. Para construir need se lee t una vez. El proceso completo es O(n + m), y una tabla de 128 contadores es la única memoria adicional.
Algoritmo
- Completa
needcon los recuentos dety establecemissingen la longitud det,left = 0y la mejor longitud enn+1. - Para cada
right: sineed[s[right]]es mayor que 0, disminuyemissing; después, disminuyeneed[s[right]]. - Mientras
missingsea 0, registra la ventana si es estrictamente más corta que la mejor. Después, aumentaneed[s[left]]; si ahora es mayor que 0, aumentamissing. Avanzaleft. - Devuelve la mejor ventana o
""si la mejor longitud sigue siendon+1.
def minWindow(s, t):
# need[c]: copies of c that t asks for minus copies inside the window.
# Positive means the window still lacks c; negative means it holds spares.
need = [0] * 128
for ch in t:
need[ord(ch)] += 1
missing = len(t) # characters of t the window does not cover yet
left = 0
best_start, best_len = 0, len(s) + 1
for right in range(len(s)):
c = ord(s[right])
if need[c] > 0: # this copy fills a gap
missing -= 1
need[c] -= 1
while missing == 0: # the window covers t: record it, then shrink
if right - left + 1 < best_len:
best_start, best_len = left, right - left + 1
c = ord(s[left])
need[c] += 1
if need[c] > 0: # gave away a copy t needs
missing += 1
left += 1
if best_len > len(s):
return ""
return s[best_start:best_start + best_len]
Errores comunes y casos límite
La mayoría de las respuestas incorrectas cuentan lo que no deben o registran la ventana en el momento equivocado.
- Contar letras en lugar de copias.
t = aannecesita dosa, así quebanno lo cubre. - Disminuir
missingpor cada carácter que entra. Una terceraaes sobrante; si disminuyemissing, el contador llega a 0 mientras a la ventana todavía le falta lan. Disminúyelo solo cuandoneedsea mayor que 0. - Aumentar
missingpor cada carácter que sale. Quitar un sobrante mantiene la ventana cubriendot; auméntalo solo cuandoneedpase a ser mayor que 0. - Registrar la ventana después del bucle de reducción. Para entonces, ya no cubre
t. Regístrala dentro del bucle, antes de quitars[left]. - Reemplazar la mejor ventana cuando la nueva tiene la misma longitud. Eso devuelve la ventana más a la derecha entre las más cortas; compara usando una desigualdad estricta de menor que.
- Usar
ncomo longitud para «no encontrado». Cuando la respuesta es toda la cadenas, su longitud también esn. Empieza enn+1para que los dos casos sean diferentes. - Una tabla de 26 posiciones indexada por
c - 'a'. Las letras mayúsculas quedan fuera de ella. Usa una posición por código de carácter.
Preguntas frecuentes4
¿Cuál es la complejidad temporal de la subcadena mínima que contiene todas las letras?
La ventana deslizante con un contador de caracteres faltantes se ejecuta en tiempo O(n + m), donde n y m son las longitudes de s y t. La construcción de la tabla lee t una vez, y cada carácter de s entra y sale de la ventana como máximo una vez, con un costo fijo por movimiento. La memoria adicional es una tabla con un contador por código de carácter, que no crece con la entrada.
¿Por qué el borde izquierdo nunca vuelve atrás?
El borde izquierdo avanza más allá de una posición solo después de que una ventana que comienza allí haya cubierto t, y esa era la ventana más corta que lo cubría desde ese inicio. Cualquier ventana que comience allí y termine más adelante es más larga, así que volver atrás nunca podría encontrar una respuesta mejor. Por eso ambos bordes avanzan una sola vez y el trabajo sigue siendo lineal.
¿Qué cuenta el contador que falta?
Es el número de copias de caracteres que t necesita y que la ventana aún no contiene: la suma de los valores positivos de need. Empieza siendo igual a la longitud de t y es 0 exactamente cuando la ventana cubre t. Las copias sobrantes nunca lo cambian, lo que permite que una sola comparación sustituya un recorrido de cada letra.
¿En qué se diferencia Minimum Window Substring de encontrar un anagrama en una cadena?
Un anagrama contiene exactamente las letras de t y ninguna otra, por lo que la ventana tiene una longitud fija de m y se desliza de un paso en un paso. Aquí, la ventana puede contener caracteres adicionales, así que su longitud forma parte de la respuesta: crece por la derecha hasta que cubre t y se reduce por la izquierda mientras siga cubriéndola.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
Python
def minWindow(s, t):
# Escribe el código aquíCaso 1
Caso 2
Caso 3
Entrada
s = "mappingtheplan" t = "nap"
Esperado
"plan"