Comprendiendo el Patrón de Ventana Deslizante

El patrón de Ventana Deslizante (Sliding Window) se utiliza para reducir la complejidad de tiempo de problemas que involucran subarreglos o subcadenas. En lugar de recalcular todo para cada rango, “deslizamos” una ventana a través de la colección, actualizando solo los elementos que entran y salen.

1. Subcadena más Larga sin Caracteres Repetidos

Encuentra la longitud de la subcadena más larga que contiene solo caracteres únicos.

function lengthOfLongestSubstring(s: string): number {
  let start = 0;
  let maxLength = 0;
  const lastSeenMap = new Map<string, number>();

  for (let end = 0; end < s.length; end++) {
    const char = s[end];

    // Si hemos visto este carácter y está dentro de nuestra ventana actual
    if (lastSeenMap.has(char) && lastSeenMap.get(char)! >= start) {
      // Mover el inicio de la ventana después de la ocurrencia anterior
      start = lastSeenMap.get(char)! + 1;
    }

    lastSeenMap.set(char, end);
    maxLength = Math.max(maxLength, end - start + 1);
  }

  return maxLength;
}

[!TIP] Mapa vs. Arreglo: Si sabes que la entrada solo contiene caracteres ASCII, usar un arreglo de tamaño 128 como mapa de frecuencias puede ser ligeramente más rápido que un objeto Map en los motores de JavaScript.

2. Máxima Cantidad de 1s Consecutivos III

Dado un arreglo binario nums y un entero k, devuelve el número máximo de 1s consecutivos si puedes voltear como máximo k ceros.

function longestOnes(nums: number[], k: number): number {
  let left = 0;
  let zeroCount = 0;
  let maxLength = 0;

  for (let right = 0; right < nums.length; right++) {
    if (nums[right] === 0) {
      zeroCount++;
    }

    // Encoger la ventana hasta que tengamos como máximo k ceros
    while (zeroCount > k) {
      if (nums[left] === 0) {
        zeroCount--;
      }
      left++;
    }

    maxLength = Math.max(maxLength, right - left + 1);
  }

  return maxLength;
}

¿Cuándo usar Ventana Deslizante?

1. Datos contiguos: Buscas un subarreglo, subcadena o un rango.
2. Optimalidad: Necesitas encontrar una propiedad máxima, mínima o la más larga/corta.
3. Tiempo Lineal: Quieres evitar $O(n^2)$ y apuntar a $O(n)$.

[!NOTE] Ventana Dinámica vs. Fija:

• Fija: El tamaño de la ventana K es constante (ej., “Suma de cada 3 elementos”).
• Dinámica: La ventana crece o se encoge según una condición (como los ejemplos anteriores).

Consejo Pro para Entrevistas

Si te piden rastrear caracteres en una ventana, tus mejores amigos son un Mapa de Hash o un Arreglo de Frecuencias. Te permiten saber en $O(1)$ si se cumple una condición antes de expandir el puntero “derecho” o encoger el puntero “izquierdo”.