Domina minimum window substring con el invariante de validez, duplicados y contraccion segura. Explicacion clara para entrevistas, haz clic y aprende.
La mayoría de los candidatos que se quedan en blanco con este problema en entrevistas no se quedan en blanco porque olvidaron el algoritmo. Se quedan en blanco porque nunca separaron las dos cosas que el problema realmente pide: cómo sabe usted que una ventana es válida y cómo sabe que es la ventana válida más pequeña. Son preguntas distintas, y confundirlas es la razón por la que tantas explicaciones de minimum window substring se quedan a medias justo cuando la persona entrevistadora se inclina hacia delante.
La buena noticia es que, en cuanto puede expresar el invariante de validez de la ventana en lenguaje sencillo, toda la solución deja de parecer un truco memorizado y empieza a sentirse como una consecuencia inevitable de la regla que ya conoce. En torno a ese cambio se construye esta guía.
Qué le está pidiendo realmente demostrar Minimum Window Substring
El problema no es 'encontrar una subcadena' — es 'demostrar que esta es la más pequeña válida'
El planteamiento estándar es: dadas la cadena `s` y la cadena `t`, encontrar la subcadena de longitud mínima de `s` que contenga todos los caracteres de `t`. Suficientemente simple de leer. El error estructural que cometen la mayoría de los candidatos es tratarlo como un problema de búsqueda cuando en realidad es un problema de demostración. Encontrar una ventana válida es fácil: cualquier ventana que cubra todo `t` sirve. La parte difícil es demostrar que la ventana que devuelve es la más pequeña, y eso requiere una definición formal de qué significa válido antes de escribir una sola línea de código.
Los candidatos que pasan directamente al bucle de dos punteros sin definir primero la validez producen explicaciones inestables. Pueden describir lo que hace el código, pero no pueden explicar por qué es seguro mover el puntero izquierdo ni por qué el mínimo que encuentran es realmente el mínimo. Esa es la laguna que detectan las personas entrevistadoras.
Cómo se ve esto en la práctica
Tome el ejemplo clásico: `s = "ADOBECODEBANC"`, `t = "ABC"`. Hay varias ventanas válidas en esa cadena: `"ADOBEC"` es válida, `"DOBECODEBA"` es válida, `"BANC"` es válida. El problema no es identificar cualquiera de ellas. El problema es llegar a `"BANC"` y poder decir, con seguridad, que no existe ninguna más pequeña. Esa afirmación requiere un argumento estructural, no solo una exploración. El algoritmo se gana el mínimo expandiendo hasta que la ventana sea válida, y luego contrayendo hasta donde la validez lo permita, registrando lo mejor que encuentra en cada estado válido. Cada paso de ese bucle es consecuencia del invariante, que es exactamente lo que la persona entrevistadora espera que usted articule.
Enuncie el invariante de validez de la ventana antes de tocar el código
El invariante que mantiene todo en orden
Aquí está el invariante, dicho de forma sencilla: una ventana es válida si y solo si, para cada carácter `c` en `t`, el número de veces que `c` aparece en la ventana actual es mayor o igual que el número de veces que `t` lo requiere. No basta con que el carácter esté presente. No basta con que los caracteres correctos estén en algún lugar de la ventana. Los conteos deben cumplir o superar los requisitos, para cada carácter, simultáneamente.
Esta es la frase que merece ir en la pizarra antes que cualquier otra cosa. Convierte la validez en un estado binario y comprobable, en lugar de una sensación vaga. Y es la base sobre la que se apoya cada otra parte del algoritmo.
Cómo se ve esto en la práctica
La implementación estándar lo sigue con dos mapas de frecuencias: `need`, que almacena el conteo requerido de cada carácter de `t`, y `window`, que almacena el conteo observado de cada carácter en la ventana actual. Una tercera variable —llámela `matched`— cuenta cuántos caracteres distintos de `t` ya están completamente satisfechos (es decir, `window[c] >= need[c]`). La ventana es válida exactamente cuando `matched == len(need)`.
Esto importa porque la validez es un estado en el que usted entra y sale a medida que se mueven los punteros. Cuando añade un carácter por la derecha y eso hace que `window[c]` pase de `need[c] - 1` a `need[c]`, incrementa `matched`. Cuando quita un carácter por la izquierda y eso hace que `window[c]` baje por debajo de `need[c]`, decrementa `matched`. El invariante siempre está satisfecho o no lo está; no hay ambigüedad, y precisamente eso es lo que hace confiable al algoritmo.
Por qué a la persona entrevistadora le importa más esto que la forma de su código
Un candidato que puede recitar el bucle de dos punteros pero no explicar por qué es correcto, desde el punto de vista de una entrevista, es un candidato que memorizó una solución. Un candidato que enuncia primero el invariante y luego deriva el bucle a partir de él es un candidato que entiende el problema. La sintaxis de la implementación se puede recuperar bajo presión. El razonamiento, no — salvo que realmente se haya apropiado de él.
El invariante es la historia de corrección. Cuando la persona entrevistadora pregunta "¿por qué es seguro contraer el puntero izquierdo aquí?", la respuesta es: porque la ventana sigue siendo válida, así que no ha perdido nada necesario. Esa respuesta solo surge de forma natural si empezó por el invariante, no por el código. Según *Introduction to Algorithms* (CLRS), el razonamiento basado en invariantes es precisamente lo que distingue a un algoritmo correcto de uno que solo produce resultados correctos en los casos de prueba que usted intentó.
Maneje los caracteres duplicados en t sin romper el conteo
Por qué 'contiene el carácter' es la prueba equivocada
El error más común en soluciones al problema de la subcadena mínima no es un fallo de sintaxis. Es conceptual: tratar la pertenencia de un carácter como si fuera cobertura. Si `t = "AABC"`, una ventana que contiene una `A`, una `B` y una `C` no es válida. Necesita dos `A`. Un candidato que comprueba `'A' in window` en lugar de `window['A'] >= need['A']` generará una solución que pasa pruebas simples y falla en cuanto aparecen duplicados.
Precisamente aquí es donde las personas entrevistadoras profundizan. Le pedirán que recorra un caso con caracteres duplicados en `t`, y si su modelo mental es "¿la ventana contiene todos los caracteres de `t`?", dará la respuesta equivocada.
Cómo se ve esto en la práctica
Suponga que `t = "AABC"`. El mapa `need` es `{'A': 2, 'B': 1, 'C': 1}`. Una ventana que contiene `"ABC"` tiene `window = {'A': 1, 'B': 1, 'C': 1}`. El conteo de `A` es 1, pero el requisito es 2. El invariante no se cumple — `matched` solo debería incrementarse para `A` cuando `window['A']` alcance 2, no cuando alcance 1. Hasta que entre esa segunda `A` en la ventana, la ventana es inválida sin importar cuántos otros caracteres cubra.
El contador `matched` maneja esto con claridad: solo incrementa cuando `window[c]` pasa de `need[c] - 1` a exactamente `need[c]`. Una aparición de `A` no dispara el incremento. La segunda sí. Por eso el enfoque basado en conteos no es una optimización, sino un requisito de corrección.
La forma sencilla de explicarlo en voz alta en una entrevista
La distinción verbal es simple: frecuencia requerida frente a frecuencia observada. Si la frecuencia observada de cada carácter cumple o supera la frecuencia requerida, la ventana es válida. Si la frecuencia observada de algún carácter queda por debajo de lo requerido, la ventana es inválida. Decirlo así hace que la lógica de duplicados parezca obvia, en lugar de un caso especial. La explicación de *sliding window* en GeeksforGeeks cubre la configuración con mapas de frecuencia, aunque raramente se hace tan explícito el marco del invariante.
Expanda a la derecha y luego contraiga a la izquierda solo mientras la ventana siga siendo válida
Por qué la contracción es segura y cuándo deja de serlo
Este es el movimiento de corrección que la mayoría de los candidatos omite. Contraer el puntero izquierdo es seguro por una única razón: la ventana sigue siendo válida después de la contracción. En el momento en que la ventana deja de ser válida —es decir, cuando `matched` cae por debajo de `len(need)`— debe dejar de contraer. Seguir contrayendo más allá de ese punto descartaría un carácter requerido, y la ventana ya no contendría todo `t`. El mínimo que registró en el último estado válido es el mínimo real para ese valor del puntero derecho.
No es una heurística. Es una consecuencia directa del invariante. Si el invariante se cumple, contraer es seguro. Si no se cumple, no lo es. El algoritmo es correcto porque respeta ese límite en todo momento.
Cómo se ve esto en la práctica
El flujo de control, dicho con claridad: expanda el puntero derecho hasta que la ventana sea válida (`matched == len(need)`). Una vez válida, registre el tamaño actual de la ventana como candidata a mínimo. Luego contraiga el puntero izquierdo —actualizando `window` y `matched` mientras avanza— y siga contrayendo mientras la ventana siga siendo válida, registrando un nuevo candidato a mínimo cada vez. Cuando la ventana se vuelva inválida, deje de contraer y vuelva a expandir el puntero derecho. Repita hasta que el puntero derecho haya recorrido toda `s`.
Ese patrón de problema de entrevista con ventana deslizante tiene dos fases anidadas: expandir-hasta-válido y luego contraer-hasta-mínimo. Ninguna de las dos fases es opcional. La fase de expansión encuentra la validez. La fase de contracción encuentra la minimalidad. Ambas son necesarias para resolver el problema correctamente.
La parte que la gente simplifica demasiado y acaba pagando
El modo de fallo es detenerse después de la primera ventana válida en lugar de seguir contrayendo. Un candidato que registra la primera ventana válida y sigue adelante obtendrá la respuesta correcta en ejemplos simples, pero fallará en cadenas donde la ventana mínima aparece después de varias rondas de expansión y contracción. El bucle `while matched == len(need)` no es un detalle: es el mecanismo que encuentra el mínimo y no solo una ventana válida. Omitirlo produce una solución aparentemente correcta pero fundamentalmente rota.
Haga un recorrido de ADOBECODEBANC hasta que el patrón deje de parecer aleatorio
Por qué ADOBECODEBANC es el ejemplo correcto para memorizar
Esta cadena es el ejemplo estándar por una razón: obliga a que ambas fases del algoritmo se desarrollen de forma visible. Es lo bastante larga para que la fase de expansión produzca varias ventanas válidas, y la fase de contracción realmente cambie la respuesta. Si puede recorrerla y explicar cada transición de estado, puede explicar el algoritmo. Según la descripción del problema *Minimum Window Substring* en LeetCode (Problema 76), el resultado esperado para `s = "ADOBECODEBANC"`, `t = "ABC"` es `"BANC"`, y llegar ahí requiere entender por qué las ventanas válidas anteriores no son el mínimo.
Cómo se ve esto en la práctica
Aquí está el recorrido clave, usando dos punteros con estado de mapa de frecuencias:
- El puntero derecho avanza: `A` → `D` → `O` → `B` → `E` → `C`. En `C`, la ventana es `"ADOBEC"`, y cubre todo `ABC`. `matched = 3`. Primera ventana válida, longitud 6.
- Contraiga a la izquierda: quite `A`. `window['A']` baja a 0, por debajo de `need['A'] = 1`. `matched` baja a 2. La ventana deja de ser válida. Pare de contraer.
- El puntero derecho avanza: `O` → `D` → `E` → `B`. La ventana es `"DOBECODEB"`. Sigue faltando `A`. Continúe avanzando.
- El puntero derecho llega a `A`. La ventana es `"DOBECODEBA"`. `matched = 3` de nuevo. Válida. Longitud 10 — peor que 6.
- Contraiga a la izquierda: quite `D`, `O`, `B`, `E`, `C`, `O`, `D`, `E`. Cada eliminación es segura porque `A`, `B` y `C` siguen cubiertos. La ventana se contrae hasta `"BA"` — pero `C` ya no está. Inválida.
- El puntero derecho avanza: `N` → `C`. La ventana es `"BANC"`. `matched = 3`. Válida. Longitud 4 — nuevo mínimo.
- Contraiga a la izquierda: quite `B`. `window['B']` baja por debajo de `need['B']`. Inválida. Pare.
- El puntero derecho se agota. Devuelva `"BANC"`.
El momento en que la ventana se vuelve más pequeña e inteligente
La transición crítica ocurre cuando el algoritmo llega a `"BANC"` tras la segunda fase de expansión. En ese punto, la ventana es válida, con longitud 4, y supera al mejor resultado anterior de 6. El algoritmo la registra. Después intenta contraer más, pierde `B` de inmediato y se detiene. Esa secuencia —válida, registrar, contraer hasta invalidar— es el invariante en acción. La respuesta `"BANC"` no es una suposición. Es la consecuencia de aplicar una regla de forma consistente.
Diga la respuesta como si la creyera en una explicación de 60 segundos
La versión que suena segura y no memorizada
Así suena una explicación de entrevista sobre minimum window substring cuando la persona candidata se apropia del invariante:
"El objetivo es encontrar la subcadena más corta de `s` que contenga cada carácter de `t` con al menos la frecuencia requerida. Usaré dos punteros y un mapa de frecuencias. El invariante clave es: una ventana es válida cuando el conteo observado de cada carácter de `t` cumple o supera su conteo requerido. Lo seguiré con un contador `matched`, que se incrementa cuando el conteo de un carácter alcanza exactamente el umbral requerido y se decrementa cuando baja por debajo.
El bucle tiene dos fases: expandir el puntero derecho hasta que la ventana sea válida, luego contraer el puntero izquierdo mientras la validez se mantenga, registrando el tamaño de la ventana cada vez. El mínimo entre todos los estados válidos es la respuesta. La complejidad temporal es O(n + m): cada puntero avanza como máximo n veces, y los mapas de frecuencia están acotados por el tamaño del conjunto de caracteres. El espacio es O(m) para los mapas, o O(1) si usa un arreglo fijo de 128 elementos para ASCII."
Cómo se ve esto en la práctica
Observe lo que hace esa explicación: empieza con el objetivo, enuncia explícitamente el invariante, describe la variable de estado, explica el bucle de dos fases y cierra con la complejidad. No empieza con "uso una ventana deslizante" y espera que la persona entrevistadora rellene los huecos. El invariante aparece en la segunda frase, no como una ocurrencia tardía. Ese orden transmite que el candidato entiende la corrección, no solo la implementación.
Conozca los errores que hacen que buenas soluciones fallen en entrevistas
Los errores clásicos: off by one, conteos desactualizados y fingir que los duplicados no importan
Tres errores explican la mayoría de los fallos en este problema de subcadena mínima.
Pertenencia en lugar de conteo. Usar `c in window` en lugar de `window[c] >= need[c]` para comprobar la validez. Falla de inmediato en cualquier `t` con caracteres duplicados.
No decrementar `matched` al contraer. Eliminar un carácter por la izquierda, actualizar `window[c]`, pero olvidar comprobar si `window[c]` ha bajado por debajo de `need[c]` y decrementar `matched` en consecuencia. La ventana parece válida más tiempo del que realmente lo está, y el mínimo se registra incorrectamente.
Registrar la mejor ventana fuera del estado válido. Actualizar la respuesta mínima cuando `matched < len(need)`, normalmente porque el candidato comprueba un nuevo mínimo en el momento equivocado del bucle, antes de confirmar la validez.
Cómo se ve esto en la práctica
El error de pertenencia produce una ventana como `"ABC"` cuando `t = "AABC"` y la declara válida. El error de conteos desactualizados produce un bucle de contracción que continúa más allá del punto de validez, descartando un carácter requerido y registrando un mínimo que en realidad no contiene todo `t`. El error de ubicación registra una ventana demasiado grande o demasiado pequeña porque la actualización ocurre en el momento incorrecto del flujo de control.
Cada uno de estos errores es estructural, no un error tipográfico. Surgen de un modelo borroso de qué significa validez, no de programar con descuido.
La tranquilidad que la mayoría de los candidatos necesita
Si ha cometido alguno de estos errores, no fue porque sea malo en algoritmos. Fue porque empezó por la forma del código y no por el invariante. En cuanto el invariante está claro —válido significa que todas las frecuencias requeridas se cumplen—, cada uno de estos errores se vuelve obviamente incorrecto antes incluso de ejecutar el código.
Explique la complejidad sin parecer que memorizó una chuleta
Por qué esto es lineal aunque los punteros se muevan mucho
La complejidad temporal es O(n + m), donde n es la longitud de `s` y m es la longitud de `t`. El argumento es simple: el puntero izquierdo y el derecho avanzan como máximo n veces cada uno, y nunca se mueven hacia atrás. El número total de operaciones sobre punteros está acotado por 2n. La preparación inicial del mapa `need` es O(m). En conjunto, eso da O(n + m). El algoritmo es lineal no por un truco ingenioso, sino por una propiedad estructural: dos punteros con estado de mapa de frecuencias, donde cada puntero es monótonamente no decreciente.
Cómo se ve esto en la práctica
La complejidad espacial es O(|Σ|), donde Σ es el conjunto de caracteres. Para un mapa de frecuencias implementado como mapa hash, el espacio está acotado por el número de caracteres distintos en `s` y `t`. En la práctica, eso es como máximo 52 para entrada alfabética sensible a mayúsculas, o 128 para ASCII completo.
Cuándo un arreglo de tamaño fijo supera a un mapa hash
Si la entrada está garantizada como ASCII, un arreglo fijo de longitud 128 suele ser más rápido en la práctica que un mapa hash: sin hashing, sin manejo de colisiones, acceso directo por índice. Si la entrada puede ser Unicode —puntos de código arbitrarios—, necesita un mapa hash porque el espacio de caracteres es demasiado grande para un arreglo fijo. Conocer esta diferencia y poder expresarla con claridad demuestra que el candidato ha pensado en compromisos reales de implementación, no solo en complejidad teórica.
Aplique el mismo patrón a los problemas adecuados, y omítalo en los incorrectos
Cuándo encaja este patrón y cuándo no
El patrón de problema de entrevista con ventana deslizante se aplica cuando: la condición de validez depende de la frecuencia de caracteres en una ventana contigua, la ventana puede expandirse y contraerse moviendo dos punteros hacia delante, y la respuesta óptima se obtiene minimizando o maximizando el tamaño de la ventana sujeto a la condición de validez. Minimum Window Substring cumple las tres.
No se aplica cuando: el orden de los caracteres dentro de la ventana importa (problemas de subsecuencia), la condición de validez requiere coincidencia no contigua, o la restricción recae sobre algo distinto de la frecuencia de caracteres. Confundir problemas de subcadena con problemas de subsecuencia es un error común de reconocimiento de patrones.
Cómo se ve esto en la práctica
La detección de anagramas en una cadena (encontrar todos los índices de inicio donde aparece una permutación de `t` en `s`) usa la misma estructura de mapa de frecuencias y dos punteros, pero la condición de validez es más estricta: conteos exactos, no "al menos", y una ventana de tamaño fijo. Minimum Window Subsequence se parece superficialmente, pero es fundamentalmente distinto: exige que los caracteres aparezcan en orden, lo que rompe por completo la lógica de contraer a la izquierda y requiere otro enfoque.
El límite queda claro en cuanto se hace la pregunta correcta: ¿la validez depende de la frecuencia en una ventana contigua, o importa el orden dentro de la ventana? Si importa el orden, este patrón no se aplica.
La lección transferible que realmente importa a las personas entrevistadoras
La habilidad real que se evalúa no es si memorizó el algoritmo de minimum window substring. Es si puede identificar el invariante que gobierna un problema, construir una máquina de estados en torno a él y razonar sobre la corrección desde esa base. Esa habilidad se transfiere a todos los problemas de ventana deslizante, y a una clase mucho más amplia de problemas en los que la clave es definir qué significa "válido" antes de escribir código. Según *The Algorithm Design Manual* de Skiena, la capacidad de articular invariantes del problema distingue de forma consistente a los candidatos que resuelven problemas de los que explican soluciones.
Cómo Verve AI puede ayudarle a prepararse para su entrevista sobre Minimum Window Substring
La parte más difícil de este problema no es escribir el código. Es explicar el invariante en voz alta, bajo presión en tiempo real, a alguien que está buscando activamente huecos. Eso es una habilidad de desempeño, y las habilidades de desempeño requieren práctica en vivo, no más lectura.
Verve AI Interview Copilot está diseñado precisamente para cubrir esa laguna. Escucha en tiempo real su explicación oral y responde a lo que realmente dijo, no a una indicación prefabricada. Cuando usted dice "uso una ventana deslizante" y se queda ahí, Verve AI Interview Copilot puede hacer la misma repregunta que haría una persona entrevistadora real: "¿Por qué es seguro contraer el puntero izquierdo?" —y usted tiene que responder, en vivo, con el invariante que domina o no domina. Esa es la práctica que importa. Verve AI Interview Copilot también permanece invisible durante sesiones de compartir pantalla a nivel de sistema operativo, así que si está haciendo una simulación con una persona compañera o una coach, la herramienta está ahí sin distraer. La explicación de 60 segundos de la Sección 6 merece ensayarse en voz alta al menos cinco veces antes de su entrevista. Verve AI Interview Copilot es la forma más rápida de obtener retroalimentación honesta e inmediata sobre si suena a comprensión o a recitación.
FAQ
P: ¿Cuál es el invariante de la ventana mínima y cómo sabe cuándo una ventana es válida?
Una ventana es válida cuando el conteo observado de cada carácter de `t` cumple o supera su conteo requerido; no basta con que el carácter esté presente, sino que debe aparecer al menos tantas veces como `t` lo exige. Usted lo sigue con un contador `matched` que es igual a `len(need)` cuando el invariante se satisface por completo. Si `matched < len(need)`, la ventana es inválida sin importar su tamaño.
P: ¿Cómo cambian los duplicados en t la lógica de conteo?
Los duplicados implican que no puede usar pruebas de pertenencia: debe comparar la frecuencia observada con la frecuencia requerida para cada carácter. Si `t = "AABC"`, una ventana necesita dos `A` para satisfacer el requisito de `A`. El contador `matched` se incrementa para `A` solo cuando `window['A']` alcanza `need['A'] = 2`, no cuando alcanza 1. Una sola `A` en la ventana no hace que la ventana sea válida.
P: ¿Cómo se contrae el puntero izquierdo sin romper la corrección?
Contrae solo mientras la ventana siga siendo válida; es decir, mientras `matched == len(need)`. Cada vez que quite un carácter por la izquierda, actualice `window[c]` y compruebe si `window[c]` ha bajado por debajo de `need[c]`. Si ha bajado, decrementa `matched` y deje de contraer. El invariante garantiza que cada ventana que registra durante la fase de contracción es realmente válida, así que el mínimo entre ellas es un mínimo verdadero.
P: ¿Cómo sonaría una explicación clara de entrevista en 60 segundos?
Empiece por el objetivo: encontrar la subcadena más corta de `s` que contenga todos los caracteres de `t` con las frecuencias requeridas. Enuncie el invariante: una ventana es válida cuando el conteo observado de cada carácter cumple su conteo requerido. Describa el mecanismo: un contador `matched` que sigue cuántos caracteres están completamente satisfechos. Explique el bucle: expanda a la derecha hasta que sea válido, contraiga a la izquierda mientras siga siendo válido, registre el mínimo en cada estado válido. Cierre con la complejidad: O(n + m) en tiempo y O(|Σ|) en espacio. Esa es la explicación completa, en orden.
P: ¿Cuáles son los errores más comunes que cometen los candidatos en este problema?
Tres errores dominan: usar pertenencia (`c in window`) en lugar de comparación de conteos (`window[c] >= need[c]`), no decrementar `matched` cuando el conteo de un carácter cae por debajo del requisito durante la fase de contracción, y registrar la mejor ventana en el momento equivocado del bucle, antes de confirmar que la ventana es válida. Los tres surgen de una definición borrosa de validez, no de errores de codificación.
P: ¿Cómo se traslada este patrón a otras preguntas de entrevista con ventana deslizante?
El patrón se aplica siempre que la validez dependa de la frecuencia de caracteres en una ventana contigua y que la respuesta óptima minimice o maximice el tamaño de la ventana. La detección de anagramas usa la misma estructura con conteos exactos y un tamaño de ventana fijo. Minimum Window Subsequence parece similar, pero requiere coincidencia ordenada, lo que rompe la lógica de contraer a la izquierda. La habilidad transferible es preguntarse: ¿la validez depende de la frecuencia en una ventana contigua, o importa el orden dentro de la ventana?
P: ¿Cómo se recorre ADOBECODEBANC paso a paso?
Expanda a la derecha hasta `"ADOBEC"`: primera ventana válida, longitud 6. Contraiga a la izquierda: quite `A`, la ventana se vuelve inválida, y pare. Expanda a la derecha hasta `"DOBECODEBA"`: válida de nuevo, longitud 10, peor. Contraiga a la izquierda lo máximo que permita la validez. Expanda a la derecha hasta `"BANC"`: válida, longitud 4, nuevo mínimo. Intente contraer: quite `B`, inválida, pare. El puntero derecho se agota. Devuelva `"BANC"`. La clave es seguir `matched` en cada paso para confirmar cuándo se entra y se sale de la validez.
Conclusión
Este problema no es un truco. Nunca lo fue. La razón por la que parece uno es que la mayoría de las explicaciones saltan directamente a la implementación y dejan el invariante implícito, lo que significa que en el momento en que una persona entrevistadora pregunta "¿por qué funciona esto?", no hay nada que decir.
El invariante es la respuesta: una ventana es válida cuando cada carácter requerido aparece al menos tantas veces como `t` exige. Todo lo demás —los mapas de frecuencia, el contador `matched`, el bucle de expandir y luego contraer— es una consecuencia directa de seguir con precisión esa condición. Una vez que se apropia del invariante, el código se deduce. Una vez que puede decir el invariante en voz alta, la explicación se deduce.
Antes de su próxima entrevista, haga dos cosas: ensaye la explicación de 60 segundos de la Sección 6 hasta que suene como un pensamiento y no como una recitación, y recorra ADOBECODEBANC a mano hasta que pueda decir en voz alta el estado de `matched` en cada paso sin mirar. Esas dos prácticas harán más por su rendimiento bajo presión que cualquier cantidad de relectura.
Verve AI
Contenido