Método de ventana deslizante

3.1 Definición del método de ventana deslizante.

Método de ventana deslizante (Sliding Window) es una técnica utilizada para resolver problemas en arrays o strings, donde un subarray (o substring) fijo se mueve sobre los datos para encontrar la solución óptima. Esto permite procesar elementos en una ventana de tamaño fijo y modificar dinámicamente la ventana según las condiciones del problema.

Esta técnica es especialmente útil para problemas relacionados con secuencias de datos, como arrays o strings, y ayuda a reducir la complejidad temporal en comparación con enfoques más ingenuos.

Principios básicos

• Inicialización de la ventana: Establece el inicio y el fin de la ventana en posiciones iniciales.
• Desplazamiento de la ventana: Desplaza secuencialmente los límites de la ventana, añadiendo elementos por un lado y quitando elementos por el otro.
• Procesamiento de la ventana: En cada paso, realiza los cálculos necesarios para la ventana actual.

Complejidad temporal y espacial del método de ventana deslizante

Complejidad temporal:

• O(n) — en la mayoría de los casos, ya que el puntero o ventana se mueve linealmente a través del array, verificando cada posible posición de la ventana.

Complejidad espacial:

• O(1) — si se usa una cantidad fija de memoria adicional para almacenar valores actuales.
• O(k) — si es necesario almacenar elementos dentro de la ventana actual de tamaño k.

3.2 Encontrar la suma máxima de un subarray.

Encontrar la suma máxima de un subarray de tamaño fijo

Problema:

Encuentra el subarray de tamaño fijo k con la suma máxima.

Solución:

Utiliza el método de ventana deslizante para mantener la suma actual del subarray y actualiza la suma máxima a medida que la ventana se desliza.

Complejidad temporal: O(n).

Ejemplo de código en Python:

def max_sum_subarray(arr, k):
    n = len(arr)
    if n < k:
        return -1
            
    window_sum = sum(arr[:k])
    max_sum = window_sum
            
    for i in range(n - k):
        window_sum = window_sum - arr[i] + arr[i + k]
        max_sum = max(max_sum, window_sum)
            
    return max_sum
        
        

3.3 Encontrar todos los anagramas de una substring en un string

Problema:

Encuentra todos los anagramas de una substring dada p en un string s.

Solución:

Utiliza el método de ventana deslizante para mantener un diccionario de frecuencias de los caracteres de la ventana actual y compáralo con el diccionario de frecuencias de la substring.

Complejidad temporal: O(n).

Ejemplo de código en Python:

from collections import Counter

def find_anagrams(s, p):
    p_count = Counter(p)
    s_count = Counter()
                
    result = []
    k = len(p)
                
    for i in range(len(s)):
        s_count[s[i]] += 1
        
        if i >= k:
            if s_count[s[i - k]] == 1:
                del s_count[s[i - k]]
            else:
                s_count[s[i - k]] -= 1
                            
        if s_count == p_count:
            result.append(i - k + 1)

    return result
        

3.4 Encontrar el subarray mínimo

Encontrar el subarray mínimo cuya suma excede un valor dado

Problema:

Encuentra el subarray mínimo cuya suma de elementos excede un valor dado S.

Solución:

Utiliza el método de ventana deslizante para expandir el borde derecho hasta que la suma sea mayor que S, luego mueve el borde izquierdo para minimizar la longitud del subarray.

Complejidad temporal: O(n).

Ejemplo de código en Python:

def min_subarray_len(S, arr):
    n = len(arr)
    min_len = float('inf')
    current_sum = 0
    left = 0
            
    for right in range(n):
        current_sum += arr[right]
                
        while current_sum >= S:
            min_len = min(min_len, right - left + 1)
            current_sum -= arr[left]
            left += 1
            
    return 0 if min_len == float('inf') else min_len