Minimum Window Substring
Recibes dos cadenas, s y t. Encuentra la subcadena más corta de s 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 también pueden aparecer otros caracteres.
Si varias subcadenas tienen la misma longitud mínima, devuelve la que esté más a la izquierda. Si ninguna 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 todos los caracteres de t, o una cadena vacía
Restricciones
1 ≤ s.length ≤ 5 × 1041 ≤ t.length ≤ 104sytcontienen únicamente 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 está más a la izquierda; cuando no existe ninguna, es
"".
Ejemplos
- Entrada
- s = "mappingtheplan"t = "nap"
- Salida
- "plan"
- Explicación
- La primera ventana desde la izquierda que contiene una
n, unaay unapesappin, cinco caracteres.plancontiene las tres en cuatro caracteres, y ninguna secuencia de tres 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
CdeCoddyestá en mayúscula; es un carácter distinto dec. Ninguna subcadena contiene unacminúscula, así que la respuesta es la cadena vacía.
Para ir más allá
Cuando t tiene pocas letras y s es larga, la mayor parte de s nunca importa. ¿Puedes hacer que la ventana salte únicamente 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 esto para evitar probar cada inicio con cada final.Avanza el borde derecho hasta que la ventana cubra
t. Después avanza el borde izquierdo mientras la ventana siga cubriendot, registrándolo cada vez. Ninguno de los bordes tiene que retroceder nunca.Mantén 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 a la ventana le falta. La ventana cubretexactamente cuandomissinges 0.
Solución
Solo importan los recuentos en una ventana, no su orden. Mueve el borde derecho hasta que la ventana cubra t, y después mueve el borde izquierdo mientras todavía lo cubra; ninguno de los bordes retrocede. Un contador de caracteres faltantes te indica de una vez si la ventana cubre t.
Amplía una ventana desde cada posición inicial
Correcto, pero no termina con las pruebas más grandes
Intuición
Fija un inicio y amplía la ventana un carácter a la vez, llevando la cuenta de cada carácter. Después de cada paso, comprueba cada una de las u letras que usa t. El primer extremo que cumpla la condición da la ventana de cobertura más corta desde este inicio, así que detente ahí. Los inicios se recorren de izquierda a derecha y solo una ventana estrictamente más corta reemplaza a la mejor, así que los empates conservan la más a la izquierda.
Si no existe ninguna ventana, cada inicio recorre s hasta el final: aproximadamente n²/2 pasos, 1.25 × 10^9 para n = 5 × 10^4.
Algoritmo
- Cuenta las copias de cada letra que pide
t. - Para cada
start, borra la tabla de conteo y mueveendhacia la derecha, añadiendos[end]. - Cuando la ventana contenga suficientes copias de cada letra, consérvala si es estrictamente más corta que la mejor y pasa al siguiente inicio.
- 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
Agregar caracteres a una ventana que cubre algo hace que siga cubriéndolo, y quitar caracteres de una ventana a la que le falta algo hace que siga faltándole. Así que, a medida que el inicio se desplaza a la derecha, el final de la ventana más corta que cubre algo nunca se desplaza a la izquierda.
No se omite ninguna ventana. Toma la mejor ventana, desde L hasta R. Para que left pase de L antes de que right llegue a R, una ventana más corta que empezara en L tendría que cubrir t. Así que, cuando right llega a R, al reducir la ventana, left avanza hasta L y se registra.
Cada extremo se mueve como máximo n veces, pero cada comprobación lee hasta u conteos: O(n·u).
Algoritmo
- Cuenta las copias que necesita
t; estableceleft = 0y la mejor longitud enn+1. - Para cada
right, añades[right]a los recuentos de la ventana. - Mientras haya suficientes copias de cada letra de
t, registra la ventana si es estrictamente más corta, eliminas[left]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 de elementos faltantes
Intuición
Reemplaza el recorrido por un solo número. Sea need[c] la cantidad de copias de c que t necesita, menos las copias que hay en la ventana; un valor negativo significa que hay copias sobrantes. Sea missing la cantidad de copias que aún le faltan a la ventana, empezando por la longitud de t. La ventana cubre t exactamente cuando missing es 0.
Un carácter que entra cuando su need es mayor que 0 llena un hueco, así que missing disminuye. Un carácter cuya eliminación hace que need supere 0 abre un hueco, así que missing aumenta. Las copias sobrantes nunca lo afectan. En banana con t = aan, missing llega a 0 por primera vez en bana, y al quitar la b sobrante, ana sigue cubriendo la cadena.
Cada carácter entra y sale una vez con un coste constante: tiempo O(n + m), con una tabla de 128 recuentos.
Algoritmo
- Completa
needcon los recuentos det; establecemissingen la longitud det,left = 0y la mejor longitud enn+1. - Para cada
right: sineed[s[right]]es mayor que 0, reducemissing; después, reduceneed[s[right]]. - Mientras
missingsea 0, registra la ventana si es estrictamente más corta. Incrementaneed[s[left]]; si ahora es mayor que 0, incrementamissing. 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
- Contar letras en vez de copias.
t = aannecesita dosa, así quebanno lo cubre. - Cambiar
missingpor cada carácter que entra o sale. Así, unaasobrante cuenta, ymissingpuede llegar a 0 mientras a la ventana le falta lan. - Reemplazar la mejor ventana cuando la longitud es igual. En el segundo ejemplo, eso devuelve
anaen el índice 3. - Usar
ncomo longitud para «no encontrado». Cuando la respuesta es toda la cadenas, su longitud también esn; empieza conn+1. - Una tabla de 26 posiciones indexada por
c - 'a'. Las letras mayúsculas, como en el tercer ejemplo, quedan fuera de ella.
Preguntas frecuentes3
¿Cuál es la complejidad temporal de Minimum Window Substring?
La ventana con 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. La memoria adicional es un contador por código de carácter.
¿Por qué el borde izquierdo nunca retrocede?
El borde izquierdo pasa una posición solo después de que la ventana que empieza allí haya cubierto t, y esa ventana era la más corta que cubría desde ese punto. Cualquier ventana desde allí que termine más tarde es más larga, así que retroceder nunca puede encontrar una respuesta mejor.
¿En qué se diferencia Minimum Window Substring de encontrar un anagrama en una cadena?
Un anagrama contiene exactamente las letras de t, por lo que su ventana tiene una longitud fija m y se desplaza de un paso a la vez. Aquí se permiten caracteres adicionales, así que la longitud forma parte de la respuesta: la ventana crece hasta cubrir t y se reduce mientras siga cubriéndola.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
def minWindow(s, t):
# Escribe el código aquíPrueba #1
Prueba #2
Prueba #3
Argumentos
s = "mappingtheplan" t = "nap"
Salida Esperada
"plan"