Ventana deslizante de longitud fija

El siguiente patrón puede resolver todos los problemas de ventana deslizante de longitud fija:

int inicio = 0, fin = 0;
int estado; // almacena el estado actual
int resultado; // almacena el resultado

while (fin < n) {
    // 1. Insertar elemento por la derecha y actualizar estado
    if (fin++ < k - 1) 
        continue;
    // 2. Actualizar resultado
    // 3. Eliminar elemento por la izquierda y actualizar estado
}

Máximo número de vocales en subcadena de longitud dada

Enlace: https://leetcode.cn/problems/maximum-number-of-vowels-in-a-substring-of-given-length/description/

Problema básico de ventana deslizante donde se cuenta el número de vocales en cada ventana.

class Solucion {
public:
    bool esVocal(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }

    int maxVocales(string s, int k) {
        int contador = 0, maximo = 0;
        for(int i = 0; i < s.length(); i++) {
            if (esVocal(s[i]))
                contador++;
            
            if (i < k - 1)
                continue;
                
            maximo = max(maximo, contador);
            
            if (esVocal(s[i - k + 1]))
                contador--;
        }
        return maximo;
    }
};

Complejidad temporal: O(n)
Complejidad espacial: O(1)

Máximo promedio de subarray I

Enlace: https://leetcode.cn/problems/maximum-average-subarray-i/description/

Aplicación directa del patrón de ventana deslizante para calcular promedios.

class Solucion {
public:
    double encontrarMaxPromedio(vector<int>& numeros, int k) {
        int suma = 0;
        int inicio = 0, fin = 0;
        int maximo = INT_MIN;
        
        while (fin < numeros.size()) {
            suma += numeros[fin];
            if (fin++ < k - 1)
                continue;
                
            maximo = max(maximo, suma);
            suma -= numeros[inicio++];
        }
        return (double)maximo / k;
    }
};
</int>

Complejidad temporal: O(n)
Complejidad espacial: O(1)

Número de subarrays de tamaño K con promedio mayor o igual al umbral

Enlace: https://leetcode.cn/problems/number-of-sub-arrays-of-size-k-and-average-greater-than-or-equal-to-threshold/description/

class Solucion {
public:
    int numeroDeSubarrays(vector<int>& arr, int k, int umbral) {
        int inicio = 0, fin = 0;
        int resultado = 0, suma = 0;
        
        while (fin < arr.size()) {
            suma += arr[fin];
            if (fin++ < k - 1)
                continue;
                
            if (suma >= umbral * k)
                resultado++;
                
            suma -= arr[inicio++];
        }
        return resultado;
    }
};
</int>

Complejidad temporal: O(n)
Complejidad espacial: O(1)

Ventana deslizante de longitud variable

Subcadena más larga sin caracteres repetidos

Enlace: https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/

Uso de tabla hash para trackear caracteres únicos en la ventana.

class Solucion {
public:
    int longitudSubcadenaSinRepetir(string s) {
        unordered_map<char int=""> frecuencia;
        int maximo = 0, izquierda = 0;
        
        for (int derecha = 0; derecha < s.length(); derecha++) {
            char actual = s[derecha];
            frecuencia[actual]++;
            
            while (frecuencia[actual] > 1) {
                frecuencia[s[izquierda]]--;
                izquierda++;
            }
            
            maximo = max(maximo, derecha - izquierda + 1);
        }
        return maximo;
    }
};
</char>

Complejidad temporal: O(n)
Complejidad espacial: O(n)

Máxima longitud de subcadena con cada carácter apareciendo como máximo dos veces

Enlace: https://leetcode.cn/problems/maximum-length-substring-with-two-occurrences/description/

class Solucion {
public:
    int maximaLongitudSubcadena(string s) {
        int maximo = 0, izquierda = 0;
        int contador[26]{};
        
        for (int derecha = 0; derecha < s.length(); derecha++) {
            char actual = s[derecha];
            contador[actual - 'a']++;
            
            while (contador[actual - 'a'] > 2) {
                contador[s[izquierda] - 'a']--;
                izquierda++;
            }
            
            maximo = max(maximo, derecha - izquierda + 1);
        }
        return maximo;
    }
};

Complejidad temporal: O(n)
Complejidad espacial: O(1)

Subarray más largo de 1s después de borrar un elemento

Enlace: https://leetcode.cn/problems/longest-subarray-of-1s-after-deleting-one-element/description/

Se permite un solo cero en la ventana para simular la eliminación de un elemento.

class Solucion {
public:
    int subarrayMasLargo(vector<int>& nums) {
        int ceros = 0, maximo = 0;
        int izquierda = 0;
        
        for (int derecha = 0; derecha < nums.size(); derecha++) {
            if (nums[derecha] == 0)
                ceros++;
                
            while (ceros > 1) {
                if (nums[izquierda] == 0)
                    ceros--;
                izquierda++;
            }
            
            maximo = max(maximo, derecha - izquierda + 1);
        }
        return maximo - 1;
    }
};
</int>

Complejidad temporal: O(n)
Complejidad espacial: O(1)

Cadena igual dentro del presupuesto

Enlace: https://leetcode.cn/problems/get-equal-substrings-within-budget/description/

Ventana deslizante que mantiene el costo total dentro del límite.

class Solucion {
public:
    int igualarSubcadena(string s, string t, int costoMaximo) {
        int maximo = 0;
        int izquierda = 0;
        
        for (int derecha = 0; derecha < s.length(); derecha++) {
            costoMaximo -= abs(s[derecha] - t[derecha]);
            
            while (costoMaximo < 0) {
                costoMaximo += abs(s[izquierda] - t[izquierda]);
                izquierda++;
            }
            
            maximo = max(maximo, derecha - izquierda + 1);
        }
        return maximo;
    }
};

Complejidad temporal: O(n)
Complejidad espacial: O(1)