Cómo implementar la ventana deslizante en Python

Una ventana deslizante mantiene un intervalo contiguo de elementos y lo desplaza por una lista o una cadena. En Python, este patrón resulta útil cuando es posible actualizar cada respuesta a partir de la ventana anterior, en lugar de volver a calcular todos sus elementos. Los ejemplos siguientes muestran tres variantes habituales: una ventana de tamaño fijo, una ventana variable con caracteres únicos y una ventana que alcanza una suma objetivo.

¿Qué es la técnica de la ventana deslizante?

Una ventana es un intervalo delimitado por las posiciones izquierda y derecha. Puede tener una longitud fija o cambiar a medida que el algoritmo añade o elimina elementos. Como sus elementos permanecen contiguos, la ventana deslizante es adecuada para tareas relacionadas con subarreglos y subcadenas; no representa directamente selecciones arbitrarias con posiciones intermedias omitidas.

Esta técnica suele reducir el trabajo repetido. Por ejemplo, después de calcular la suma de una ventana, desplazarla una posición consiste en restar el valor que sale y sumar el que entra. Esa actualización tarda tiempo constante. La complejidad total depende del algoritmo concreto y de sus estructuras de datos, por lo que la ventana deslizante no garantiza una mejora ni un tiempo O(n) para todos los problemas.

Implementación de una ventana deslizante para hallar la suma máxima de un subarreglo de tamaño K

Dada una lista de números y un tamaño de ventana positivo k, primero se suman los k valores iniciales. Después, se avanza la ventana de una posición en una, actualizando la suma con el valor que sale y el que entra. Se conserva la mayor suma encontrada. Este ejemplo devuelve None si k no es positivo o si supera la longitud de la lista, de modo que el contrato de entrada queda explícito.

En la lista [2, 1, 5, 1, 3, 2], con k = 3, las ventanas son [2, 1, 5], [1, 5, 1], [5, 1, 3] y [1, 3, 2]. El programa imprime la mayor suma. Tarda O(n) y usa O(1) de espacio adicional, donde n es la longitud de la lista.

def max_sum_subarray(values, k):
    if k <= 0 or k > len(values):
        return None

    window_sum = sum(values[:k])
    best_sum = window_sum

    for right in range(k, len(values)):
        window_sum += values[right] - values[right - k]
        best_sum = max(best_sum, window_sum)

    return best_sum

values = [2, 1, 5, 1, 3, 2]
k = 3
print(max_sum_subarray(values, k))

Este código de ejemplo está disponible para que lo ejecutes; aquí no se afirma que se haya ejecutado ni se proporciona un resultado de ejecución.

Ventana deslizante para encontrar la subcadena más larga sin caracteres repetidos

En este problema, la ventana no contiene caracteres repetidos. Se desplaza la posición derecha por la cadena y se añade cada carácter nuevo a un conjunto. Si el carácter ya está en el conjunto, se avanza la posición izquierda y se eliminan del conjunto los caracteres que van saliendo hasta quitar el duplicado. Una vez restablecida la condición, se actualiza la longitud máxima.

Cada posición avanza como máximo una vez, y cada carácter se añade al conjunto y se elimina de él como máximo una vez. Por tanto, para una cadena de longitud n, el algoritmo tarda O(n) y usa O(min(n, tamaño del alfabeto)) de espacio. Python recorre puntos de código Unicode; un grafema que una persona percibe como un solo carácter, como una letra base combinada con una marca, puede contener más de un punto de código.

def longest_unique_substring_length(text):
    window_chars = set()
    left = 0
    best_length = 0

    for right, char in enumerate(text):
        while char in window_chars:
            window_chars.remove(text[left])
            left += 1
        window_chars.add(char)
        best_length = max(best_length, right - left + 1)

    return best_length

text = "abcabcbb"
print(longest_unique_substring_length(text))

Este código de ejemplo está disponible para que lo ejecutes; aquí no se afirma que se haya ejecutado ni se proporciona un resultado de ejecución.

Ventana deslizante para hallar la suma del subarreglo más pequeño

Dada una suma objetivo, este enfoque encuentra el subarreglo contiguo más corto cuya suma sea al menos igual a ese objetivo. Requiere que todos los valores sean no negativos: cuando la suma acumulada alcanza el objetivo, quitar un valor por la izquierda no puede aumentarla, así que reducir la ventana permite buscar un intervalo válido más corto. Con valores negativos, ese razonamiento deja de ser válido y hace falta otro algoritmo.

La función devuelve 0 si no existe ningún subarreglo que cumpla la condición. Con valores no negativos y un objetivo positivo, cada posición se añade y se elimina como máximo una vez, por lo que el tiempo es O(n) y el espacio adicional es O(1). El código acepta un objetivo no positivo y devuelve una respuesta de longitud cero, ya que no se necesitan elementos para alcanzarlo.

def min_subarray_length(target, values):
    if target <= 0:
        return 0

    left = 0
    running_sum = 0
    shortest = len(values) + 1

    for right, value in enumerate(values):
        running_sum += value
        while running_sum >= target:
            shortest = min(shortest, right - left + 1)
            running_sum -= values[left]
            left += 1

    return 0 if shortest > len(values) else shortest

values = [2, 3, 1, 2, 4, 3]
target = 7
print(min_subarray_length(target, values))

Este código de ejemplo está disponible para que lo ejecutes; aquí no se afirma que se haya ejecutado ni se proporciona un resultado de ejecución.

Conclusión

La ventana deslizante es una forma útil de razonar sobre intervalos contiguos de una lista o una cadena. Conviene usar una ventana fija cuando se conoce su tamaño y ajustar sus límites cuando una condición, como la unicidad de los caracteres o una suma objetivo, determina el intervalo. Antes de aplicar este patrón, comprueba que el estado que mantienes se pueda actualizar al desplazar la ventana y que las suposiciones del algoritmo sean válidas para los datos de entrada. Estos ejemplos cubren problemas habituales de entrevistas de Python, aunque otras restricciones pueden requerir un enfoque distinto.

Preguntas frecuentes

1. ¿Cuándo debería usar una ventana deslizante? Cuando el problema trate de subarreglos o subcadenas contiguos y sea posible actualizar el resultado actual al mover uno o ambos límites.
2. ¿Todos los algoritmos de ventana deslizante son O(n)? No. Estos ejemplos tienen complejidad lineal porque el desplazamiento de los límites y las actualizaciones de cada paso están acotados. Otros algoritmos pueden hacer más trabajo en cada desplazamiento.
3. ¿Puedo usar esta ventana para la suma mínima si hay números negativos? No tal como está escrita. La regla para reducir la ventana depende de que los valores sean no negativos; al quitar un elemento negativo, la suma puede aumentar.
4. ¿Cuál es la diferencia entre un subarreglo y una subsecuencia? Un subarreglo es contiguo. Una subsecuencia puede omitir posiciones, siempre que conserve el orden, así que una ventana no recorre todas las subsecuencias.