Entrevista técnica: ¿Cómo resolver Minimum Window Substring?

El problema y cuándo aplica

Dadas las cadenas s y t, encuentra la subcadena contigua más corta de s que contenga cada carácter de t al menos tantas veces como aparece en t. La coincidencia distingue entre mayúsculas y minúsculas. Por ejemplo:

s = "ADOBECODEBANC"
t = "ABC"
output = "BANC"

Si t = "AABC", una ventana candidata necesita al menos dos caracteres A, uno B y uno C. Una verificación de pertenencia a un conjunto pierde este requisito de multiplicidad, lo cual constituye el error semántico más común en este problema.

Las restricciones son 1 <= s.length, t.length <= 100000, y ambas cadenas contienen únicamente letras en mayúsculas y minúsculas del alfabeto inglés. Si existe una respuesta, la más corta es única. Devuelve una cadena vacía cuando ninguna ventana cubra t. La implementación siguiente también maneja defensivamente un t vacío y un s más corto que t, aunque esas entradas quedan fuera de las restricciones estándar.

Registros públicos recientes de entrevistas de ingeniería de software continúan mostrando Minimum Window Substring, incluida una variación donde t no tiene caracteres duplicados. Tanto las plataformas de código en inglés como en chino conservan este problema. Su habilidad fundamental reside en transformar una búsqueda de intervalo mínimo global en un estado mantenido incrementalmente, por lo que la categoría precisa es coding; el lenguaje del ejemplo no cambia dicha clasificación.

Qué evalúa el entrevistador

La primera señal es el modelado preciso. Una respuesta sólida formula “contiene t” como una restricción de frecuencias: para cada carácter objetivo c, la ventana actual debe satisfacer window[c] >= need[c]. Simplemente afirmar que todos los caracteres objetivo han aparecido no puede manejar t = "AA".

La segunda señal es reconocer la monotonicidad detrás del enfoque base cuadrático. Mover el límite derecho solo agrega caracteres, por lo que una ventana válida sigue siendo válida al expandirse. Para un límite derecho fijo, mover el límite izquierdo elimina caracteres. Una vez que la ventana es válida, puede contraerse hasta volverse apenas inválida, registrando candidatos más cortos a lo largo del proceso.

La tercera señal es comprimir la verificación de validez. Escanear toda la tabla de frecuencias en cada movimiento pierde el límite lineal. La implementación utiliza formed para el número de clases de caracteres objetivo cuya frecuencia requerida se ha alcanzado, con required = need.size. formed aumenta cuando una frecuencia iguala por primera vez su requisito y disminuye cuando la eliminación la sitúa por debajo de dicho requisito. Las copias excedentes no se cuentan dos veces.

Por último, el candidato debe justificar la correctitud y los casos límite: por qué se examina la ventana válida más corta para cada límite derecho, por qué los extremos izquierdos descartados no pueden producir un mejor candidato futuro y por qué cada puntero se mueve como máximo s.length veces.

Preguntas para clarificar antes de responder

• ¿La coincidencia distingue mayúsculas y minúsculas? En este caso, sí. Si la coincidencia debiera ignorar mayúsculas y minúsculas, define primero la normalización; la normalización puede alterar

el mapeo de vuelta a los índices de la cadena original.

• ¿“Contiene” preserva el orden de t? No. Este problema solo requiere cobertura de frecuencias. Exigir orden produce el

problema Minimum Window Subsequence, para el cual esta condición de validez no funciona.

• ¿Los caracteres objetivo duplicados se cuentan por separado? Sí. t = "AABC" requiere dos caracteres A, lo cual motiva directamente el uso de un

mapa de frecuencias.

• ¿Qué sucede si varias de las ventanas más cortas empatan? El problema estándar garantiza unicidad. Sin esa garantía, esta

implementación devuelve la primera ventana más corta porque solo se actualiza ante una longitud estrictamente menor.

• ¿Cuál es el conjunto de caracteres? Las entradas son letras del alfabeto inglés, por lo que indexar unidades de código UTF-16 de JavaScript no puede dividir un

carácter permitido. Para Unicode arbitrario, primero define si la coincidencia opera sobre puntos de código (code points) o grupos de grafemas percibidos por el usuario (grapheme clusters).

• ¿Puede estar vacía alguna de las cadenas? Las restricciones estándar excluyen cadenas vacías. La función de ejemplo devuelve una cadena vacía para un

t vacío, un s vacío o si s.length < t.length.

• ¿La función debe devolver texto o índices? El problema principal devuelve texto. Para índices, devuelve

[bestStart, bestStart + bestLength) sin cambiar el escaneo central.

Estas preguntas pueden modificar el predicado de validez, la representación de índices o la regla de salida. La preferencia de lenguaje, los nombres de variables y la implementación específica de la tabla hash no alteran la elección del algoritmo.

Estructura de respuesta en 30 segundos

“Contaré las frecuencias objetivo en need y mantendré una ventana con dos punteros. Conforme el puntero derecho se expande, formed aumenta únicamente cuando una clase de caracteres alcanza por primera vez su requisito. Una vez que todas las clases están satisfechas, registro la respuesta y avanzo el puntero izquierdo hasta que la ventana se vuelve inválida. Eso examina la ventana válida más corta para cada extremo derecho. Ambos punteros se mueven únicamente hacia la derecha, por lo que cada posición entra y sale a lo sumo una vez: tiempo O(|s| + |t|) y espacio de mapa de frecuencias O(u).”

Análisis detallado paso a paso

Paso 1: Usar el enfoque base para exponer el trabajo repetido.

Para cada extremo izquierdo, uno puede extender un extremo derecho mientras mantiene las frecuencias y detenerse en la primera ventana válida. Esto evita volver a contar cada subcadena, pero aún puede reescanear la mayor parte de s desde cada extremo izquierdo, tomando un tiempo de O(|s|^2 + |t|). Recalcular cada subcadena desde cero puede ser cúbico.

Aquí, u es el número de caracteres distintos en t, a lo sumo 52 bajo la restricción de letras inglesas. El diseño del estado sigue siendo la parte importante de la solución lineal; un alfabeto pequeño no debe ocultar una verificación de validez incorrecta.

Paso 2: Definir suficiente estado para una verificación de validez en tiempo constante.

need almacena frecuencias objetivo. window almacena frecuencias de caracteres objetivo en la ventana actual. required = need.size es el número de clases de caracteres a satisfacer, y formed es el número de las que han alcanzado su frecuencia requerida. La ventana es válida exactamente cuando formed === required.

Las actualizaciones deben vincularse con cruzar un umbral de requisito:

after adding c: window[c] changes from need[c]-1 to need[c], so formed += 1
after adding c: window[c] changes from need[c] to need[c]+1, so formed is unchanged
before removing c: window[c] equals need[c], so removal causes formed -= 1
before removing c: window[c] exceeds need[c], so removal leaves formed unchanged

Tratar a formed como un conteo simple de caracteres objetivo facilita sobrecontar copias sobrantes. Incrementar en cada carácter objetivo sin limitar la contribución marcaría incorrectamente a t = "AABC" como cubierto demasiado pronto.

Paso 3: Fijar el orden de expansión, registro y contracción.

El puntero derecho incluye a s[right] y actualiza el estado. Cuando la ventana se vuelve válida, el bucle interno primero considera [left, right] para la respuesta y luego se prepara para eliminar s[left]. Si la eliminación hace que una clase de caracteres sea deficiente, decrementa formed, reduce la frecuencia y avanza left.

Registrar antes de eliminar evita omitir un candidato válido. Probar igualdad antes de decrementar la frecuencia hace que la transición de umbral sea explícita. Una implementación correcta puede decrementar primero y probar si el valor queda por debajo del requisito, pero la explicación y la condición deben usar el mismo orden.

Paso 4: Implementar el escaneo lineal.

export function minWindow(s: string, t: string): string {
  if (t.length === 0 || s.length < t.length) return "";

  const need = new Map<string, number>();
  for (const char of t) {
    need.set(char, (need.get(char) ?? 0) + 1);
  }

  const window = new Map<string, number>();
  const required = need.size;
  let formed = 0;
  let left = 0;
  let bestStart = 0;
  let bestLength = Number.POSITIVE_INFINITY;

  for (let right = 0; right < s.length; right += 1) {
    const char = s[right];
    const target = need.get(char);

    if (target !== undefined) {
      const nextCount = (window.get(char) ?? 0) + 1;
      window.set(char, nextCount);
      if (nextCount === target) formed += 1;
    }

    while (formed === required) {
      const length = right - left + 1;
      if (length < bestLength) {
        bestStart = left;
        bestLength = length;
      }

      const leftChar = s[left];
      const leftTarget = need.get(leftChar);
      if (leftTarget !== undefined) {
        const currentCount = window.get(leftChar) ?? 0;
        if (currentCount === leftTarget) formed -= 1;
        window.set(leftChar, currentCount - 1);
      }
      left += 1;
    }
  }

  return Number.isFinite(bestLength)
    ? s.slice(bestStart, bestStart + bestLength)
    : "";
}

La implementación almacena conteos únicamente para caracteres objetivo. Los caracteres no objetivo aún afectan la longitud de la ventana y su límite izquierdo, por lo que no pueden eliminarse de s por adelantado; simplemente no necesitan entradas en el mapa de frecuencias.

Paso 5: Declarar los invariantes y demostrar la correctitud.

Al final de cada iteración del bucle externo, se cumplen los siguientes hechos:

1. window[c] equivale al conteo real del carácter objetivo c en el intervalo actual [left, right].
2. formed equivale exactamente al número de clases objetivo que satisfacen window[c] >= need[c].
3. Después de que finaliza el bucle interno, la ventana actual es inválida. La última ventana válida recién examinada fue la ventana válida más corta para

ese extremo right.

1. left se mueve únicamente hacia la derecha. Cualquier extremo izquierdo previo ya superado crearía una ventana más larga para el mismo extremo derecho,

y extender el extremo derecho más adelante no puede hacer que supere a un candidato ya considerado en ese extremo anterior.

La ventana inicial vacía satisface los dos primeros invariantes. Añadir el carácter derecho actualiza su conteo real, y la regla de umbral preserva el segundo invariante. Mientras la ventana sea válida, el algoritmo registra el candidato antes de cada eliminación, de modo que examina todos los límites izquierdos válidos que terminan en el right actual hasta que los dos primeros invariantes indican que la ventana es inválida. Por inducción sobre los extremos derechos, el algoritmo examina la ventana válida más corta para cada uno de ellos. El óptimo global debe encontrarse entre esos candidatos, por lo que la respuesta registrada es correcta.

Paso 6: Rastrear un objetivo con caracteres duplicados.

Sean s = "AAABBC" y t = "AABC":

need = {A:2, B:1, C:1}, required = 3
right=0, A:1  formed=0
right=1, A:2  formed=1
right=2, A:3  formed=1    surplus A does not count twice
right=3, B:1  formed=2
right=4, B:2  formed=2    surplus B does not count twice
right=5, C:1  formed=3    [0,5] is valid
remove A at index 0: A:2, still valid; record [1,5] = "AABBC"
remove another A: A:1, formed falls to 2, so contraction stops

Este seguimiento valida tres detalles independientes: una frecuencia requerida superior a uno, la ausencia de doble conteo por encima del requisito y la contracción continua tras eliminar una copia excedente.

Paso 7: Analizar la complejidad con precisión.

Construir need escanea t una vez. El puntero derecho escanea s una vez, y el puntero izquierdo puede moverse de 0 a s.length solo una vez a lo largo de toda la ejecución. El trabajo acumulado del bucle interno while es, por tanto, O(|s|). Con operaciones de mapa que toman en promedio O(1), el tiempo total es O(|s| + |t|). Los dos mapas de frecuencia almacenan como máximo u caracteres objetivo, por lo que el espacio extra es O(u); bajo la restricción de letras inglesas, u <= 52.

Paso 8: Verificar con un oráculo y propiedades.

Como mínimo, las pruebas fijas deben cubrir:

("ADOBECODEBANC", "ABC") -> "BANC"   standard mixed input
("AAABBC", "AABC")       -> "AABBC"  duplicate requirement
("a", "a")               -> "a"      minimum size
("a", "A")               -> ""       case-sensitive and impossible
("abc", "abcd")          -> ""       s is shorter than t
("abc", "")              -> ""       defensive empty target

Para cadenas aleatorias cortas, compara contra un oráculo cuadrático que enumere cada intervalo. Verifica tres propiedades del resultado optimizado: es una subcadena contigua de s, sus frecuencias cubren t y ningún intervalo más corto cubre t. Las pruebas diferenciales son especialmente efectivas para exponer un formed sobrecontado, longitudes de respuesta con errores por uno (off-by-one) y un orden de eliminación incorrecto.

Cuando s es diminuto, la operación es puntual y el rendimiento no tiene restricciones, la versión cuadrática es más corta y puede ser más segura de escribir bajo la presión de la entrevista. Con un límite de longitud de 100000 y un objetivo explícito de tiempo lineal, la ventana deslizante es la solución final apropiada.

Respuesta de muestra de alta calidad

“Primero confirmaría que la contención se basa en las frecuencias de los caracteres, que el orden no importa y que la coincidencia distingue mayúsculas de minúsculas. Un enfoque base fija cada extremo izquierdo y se expande a la derecha, lo cual resulta cuadrático en el peor caso. Este problema posee una monotonicidad útil: agregar un carácter derecho no puede invalidar una ventana válida, y una vez que una ventana es válida, avanzar el extremo izquierdo puede encontrar la ventana válida más corta que termina en dicho extremo derecho.

Almacenaré las frecuencias de t en need y las frecuencias objetivo actuales en window. También mantendré formed, el número de clases de caracteres que han alcanzado su requisito. Agregar un carácter incrementa formed solo cuando su conteo alcanza exactamente el conteo requerido. Mientras la ventana sea válida, la registro antes de eliminar el carácter izquierdo. Si ese carácter se encuentra exactamente en su conteo requerido antes de la eliminación, quitarlo hace que la clase sea deficiente, por lo que decremento formed.

Los invariantes clave son que window coincide con los conteos reales en [left, right] y que formed coincide con el número de clases objetivo satisfechas. El bucle interno verifica cada límite izquierdo válido para cada extremo derecho y se detiene justo después de pasar el más corto válido. El óptimo global se encuentra entre esos candidatos. Ambos punteros se mueven solo hacia la derecha, por lo que cada posición entra y sale a lo sumo una vez. El tiempo es O(|s| + |t|) y el espacio es O(u). Probaría con un objetivo con duplicados, casos sin solución, entradas de un solo carácter, diferencias de mayúsculas/minúsculas y cadenas cortas aleatorias frente a un oráculo de fuerza bruta.”

Errores comunes

• Guardar solo un conjunto de caracteres objetivo → los requisitos de duplicados desaparecen → almacena frecuencias requeridas.
• Incrementar el conteo de coincidencias por cada carácter objetivo agregado → las copias excedentes crean una falsa validez → **incrementa formed

solo en la primera transición al conteo requerido.**

• Decrementar siempre formed al eliminar un carácter objetivo → eliminar una copia excedente mantiene la ventana válida → **decrementa

solo cuando el conteo previo a la eliminación coincida con el requisito.**

• Contraer solo una vez tras volverse válida → se omiten ventanas más cortas que terminan en el mismo límite derecho → **utiliza un bucle while

hasta que la ventana se vuelva inválida por primera vez.**

• Mover left antes de registrar la respuesta → un mínimo válido puede pasarse por alto o medirse desfasado por uno → **mide

[left, right] primero.**

• Escanear todo need tras cada movimiento de puntero → la verificación de validez añade un factor de u → **mantén el conteo de clases satisfechas

incrementalmente.**

• Resolver un problema de subsecuencia → pueden omitirse posiciones dentro del resultado, por lo que la respuesta deja de ser contigua → **representa

cada ventana como un intervalo de índices continuo.**

• Filtrar caracteres no objetivo y luego extraer subcadenas del texto original con los índices filtrados → las posiciones filtradas no corresponden

directamente a las de origen → mantén los punteros en la cadena original e ignora los no objetivos únicamente en los mapas.

• Calificar el bucle interno como cuadrático → esto ignora la monotonicidad global del puntero izquierdo → **amortiza considerando que cada posición sale como

máximo una vez.**

• Probar únicamente el ejemplo estándar → los duplicados, los casos imposibles y la distinción de mayúsculas y minúsculas quedan sin probar → **agrega casos de prueba

adversarios fijos y un oráculo aleatorio.**

Preguntas de seguimiento y respuestas

Pregunta de seguimiento 1: ¿Por qué contar clases de caracteres satisfechas en lugar del total de caracteres coincidentes?

Cualquiera de los dos estados puede respaldar un algoritmo correcto, pero contar clases hace que las transiciones de umbral sean explícitas. Para need[A] = 2, la clase se satisface únicamente cuando window[A] pasa de 1 a 2; un tercer A no cambia ese estado. La eliminación anula el estado solo cuando el conteo pasa de 2 a 1. Un contador de caracteres totales debe incrementarse únicamente mientras window[c] <= need[c] y usar una regla de eliminación simétrica, la cual es más fácil de formular erróneamente.

Pregunta de seguimiento 2: ¿Qué se puede simplificar si t no tiene caracteres duplicados?

Cada valor en need es 1, por lo que window puede representarse mediante conteos de caracteres objetivo o mediante un conjunto emparejado con conteos de ocurrencias. Aun así, pueden aparecer copias repetidas del mismo objetivo en la ventana, y eliminar una copia puede dejar la clase satisfecha. Mantener la implementación general basada en frecuencias añade un sobrecosto constante mínimo y maneja directamente el problema original.

Pregunta de seguimiento 3: ¿Qué ocurre si los caracteres deben aparecer en el orden especificado por t?

Ese es el problema Minimum Window Subsequence. La cobertura de frecuencias ya no demuestra validez: s = "cba" cubre las frecuencias de t = "abc" pero tiene el orden incorrecto. Una solución puede usar programación dinámica para retener la posición inicial de cada prefijo coincidente, o escaneos hacia adelante y hacia atrás alrededor de extremos candidatos. Su complejidad requiere un nuevo análisis, y formed === required no puede reutilizarse como la condición de validez.

Pregunta de seguimiento 4: ¿Cómo devolverías todas las ventanas más cortas que empatan?

Sin la garantía de unicidad, mantén bestLength como antes. Cuando aparezca una ventana más corta, vacía la lista de resultados y añade ese intervalo. Cuando aparezca una ventana de igual longitud, agrégala. Si rutas de búsqueda separadas pudieran redescubrir el mismo intervalo de texto, deduplica mediante [left, right]; este recorrido de dos punteros visita cada intervalo a lo sumo una vez, por lo que aquí no se necesita un conjunto adicional.

Pregunta de seguimiento 5: ¿Qué pasa si s es un flujo de caracteres que no cabe en memoria?

Las frecuencias requeridas y el estado de los punteros aún pueden actualizarse en línea, pero devolver el texto original requiere retener el intervalo candidato actual. Una cola puede almacenar caracteres desde left hasta la posición más nueva junto con desplazamientos globales. Si no aparece ninguna ventana válida durante mucho tiempo, ese búfer puede aproximarse a la totalidad del flujo leído hasta ese momento. Devolver solo una longitud y desplazamientos permite mayor compresión en torno a las posiciones de los caracteres objetivo; devolver texto requiere una política explícita de ventana máxima o almacenamiento externo.

Pregunta de seguimiento 6: ¿Cómo admitirías texto Unicode arbitrario?

Primero define la unidad de coincidencia. Para puntos de código Unicode, itera por punto de código y retén los desplazamientos de unidades de código UTF-16 correspondientes para extraer la subcadena original de JavaScript. Un carácter percibido por el usuario puede contener varios puntos de código; hacer coincidir grupos de grafemas requiere un segmentador confiable. La normalización también cambia la definición de igualdad de caracteres, por lo que debe aplicarse consistentemente antes del conteo mientras se preserva el mapeo al texto fuente.

Pregunta de seguimiento 7: ¿Cómo puedes confiar en el oráculo de pruebas aleatorias?

El oráculo se ejecuta únicamente sobre cadenas cortas, por lo que puede enumerar cada [left, right], recontar cada intervalo directamente y elegir por longitud y posición inicial. Su flujo de control es deliberadamente diferente del algoritmo optimizado, lo que lo hace lento pero fácil de auditar. Valida el oráculo primero con ejemplos fijos, luego compara la longitud del resultado, la contigüidad y la cobertura de frecuencia durante pruebas diferenciales aleatorias para reducir la probabilidad de un error compartido.