El subarreglo más largo de solo 0 o 1 con al menos K voltea

Dado un arreglo binario a[] o tamaño N y un entero K , la tarea es encontrar el subarreglo más largo que consta de solo 1 o solo 0 cuando se pueden voltear como máximo K elementos (es decir, cambiar 1 a 0 o 0 a 1).

Ejemplos:

Entrada: a[] = {1, 0, 0, 1, 1, 0, 1}, K = 1.
Salida: 4
Explicación: Cambia el elemento del índice 0 (índice basado en 0) a 0. 
Luego, el subarreglo máximo con todos los 0 tendrán una longitud de 3 [0-2]
Cambia el índice 5 a 1. El subarreglo máximo con todos los 1 tendrá una longitud de 4 [3-6] 
Entonces el máximo de (3, 4) es 4. Entonces la respuesta es 4 para este caso de prueba.

Entrada : a[] = {1, 0, 0, 1, 0, 1, 0, 1, 0, 1}, K = 2.
Salida : 6
Explicación : cambie 2-1 a 0 o 2-0 a 1. 
Entonces, después de cambiar el elemento de índice 6 y 8 a 1,  
la longitud máxima del subarreglo que consta de solo 1 es 5 [5 a 9] .
Voltee el elemento de índice 3 y 5 a 0, entonces la longitud máxima 
del subarreglo que consta de solo 0 es 6 [1 a 6] 
El máximo de ambos es 6. Entonces, la respuesta es 6 para esta entrada. 

Enfoque: este problema se puede resolver utilizando el enfoque de dos punteros y el algoritmo de ventana deslizante basado en la siguiente idea. 

Ejecutar el bucle dos veces: 

• Un ciclo para mantener el subsegmento [l, r] para que no contenga más de K 0 y encontrar la longitud máxima del subarreglo que contiene solo 1 y
• Segundo ciclo para mantener el subsegmento [l, r] para que no contenga más de K 1 y encontrar la longitud máxima del subarreglo que contiene solo 0. 

Luego devuelva el máximo de ambas longitudes.

Siga los pasos dados para resolver el problema:

• Encontrar el subarreglo más largo que contiene solo 1 con un máximo de K -voltea:
  • Declare la variable cnt y un puntero entero a la izquierda que apuntará al índice 0 al principio.
  • Ahora ejecute un ciclo de 0 a N y en cualquier posición: 
    • Si arr[i] es igual a 0, entonces aumente la variable cnt .
    • En cualquier posición, si el cnt es mayor que K , mueva el puntero izquierdo hacia el lado derecho y verifique nuevamente si arr[left] es igual a 0 ,  
    • Luego disminuya la variable cnt y ejecute este bucle hasta que cnt sea mayor que K .
  • Almacene la longitud máxima del subarreglo que contiene solo 1 y calcule esta longitud como ( índice actual – puntero izquierdo + 1 ).
• Encuentre el subarreglo más largo que contenga solo 0 con un máximo de K-flips y almacene su longitud de manera similar.
• Devuelve el máximo entre las dos longitudes máximas.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the longest subarray
// following the given conditions
int longestSubSeg(int arr[], int N, int K)
{
    int cnt = 0;
    int left = 0;
    int maximum_len1 = 0;
    int maximum_len0 = 0;
 
    // Finding length of maximum subarray
    // containing 1's only with atmost k flips
    for (int i = 0; i < N; i++) {
        if (arr[i] == 0)
            cnt++;
 
        while (cnt > K) {
            if (arr[left] == 0)
                cnt--;
            left++;
        }
        maximum_len1 = max(maximum_len1, i - left + 1);
    }
 
    // Set these variables to 0 for further use
    cnt = 0;
    left = 0;
 
    // Finding length of maximum subarray
    // containing 0's only with atmost k flips
    for (int i = 0; i < N; i++) {
        if (arr[i] == 1)
            cnt++;
 
        while (cnt > K) {
            if (arr[left] == 1)
                cnt--;
            left++;
        }
        maximum_len0 = max(maximum_len0, i - left + 1);
    }
 
    return max(maximum_len1, maximum_len0);
}
 
// Driver code
int main()
{
    int arr[] = { 1, 0, 0, 1, 0, 1, 0, 1 };
    int K = 2;
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function call
    cout << longestSubSeg(arr, N, K);
    return 0;
}

// Java program for the above approach
 
import java.io.*;
 
class GFG {
 
    // Function to find the longest subarray
    // following the given conditions
    static int longestSubSeg(int arr[], int N, int K)
    {
        int cnt = 0;
        int left = 0;
        int max_len1 = 0;
        int max_len0 = 0;
 
        // Finding length of maximum subarray
        // containing 1's only with atmost k flips
        for (int i = 0; i < N; i++) {
            if (arr[i] == 0)
                cnt++;
 
            while (cnt > K) {
                if (arr[left] == 0)
                    cnt--;
                left++;
            }
            max_len1 = Math.max(max_len1, i - left + 1);
        }
 
        // Intialize with again 0 for further use
        left = 0;
        cnt = 0;
 
        // Finding length of maximum subarray
        // containing only 0's with atmost k flips
        for (int i = 0; i < N; i++) {
            if (arr[i] == 1)
                cnt++;
 
            while (cnt > K) {
                if (arr[left] == 1)
                    cnt--;
                left++;
            }
            max_len0 = Math.max(max_len0, i - left + 1);
        }
 
        return Math.max(max_len1, max_len0);
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int a[] = { 1, 0, 0, 1, 0, 1, 0, 1 };
        int K = 2;
        int N = a.length;
 
        // Function call
        System.out.println(longestSubSeg(a, N, K));
    }
}

// C# program for the above approach
 
using System;
 
public class GFG {
 
    // Function to find the longest subarray following the
    // given conditions
    static int longestSubSeg(int[] arr, int N, int K)
    {
        int cnt = 0;
        int left = 0;
        int max_len1 = 0;
        int max_len0 = 0;
 
        // Finding length of maximum subarray containing 1's
        // only with atmost k flips
        for (int i = 0; i < N; i++) {
            if (arr[i] == 0)
                cnt++;
 
            while (cnt > K) {
                if (arr[left] == 0)
                    cnt--;
                left++;
            }
            max_len1 = Math.Max(max_len1, i - left + 1);
        }
 
        // Intialize with again 0 for further use
        left = 0;
        cnt = 0;
 
        // Finding length of maximum subarray containing
        // only 0's with atmost k flips
        for (int i = 0; i < N; i++) {
            if (arr[i] == 1)
                cnt++;
 
            while (cnt > K) {
                if (arr[left] == 1)
                    cnt--;
                left++;
            }
            max_len0 = Math.Max(max_len0, i - left + 1);
        }
 
        return Math.Max(max_len1, max_len0);
    }
 
    static public void Main()
    {
 
        // Code
        int[] a = { 1, 0, 0, 1, 0, 1, 0, 1 };
        int K = 2;
        int N = a.Length;
 
        // Function call
        Console.WriteLine(longestSubSeg(a, N, K));
    }
}
 
// This code is contributed by lokesh (lokeshmvs21).

<script>
    // JavaScript program for the above approach
 
 
    // Function to find the longest subarray
    // following the given conditions
    const longestSubSeg = (arr, N, K) => {
        let cnt = 0;
        let left = 0;
        let maximum_len1 = 0;
        let maximum_len0 = 0;
 
        // Finding length of maximum subarray
        // containing 1's only with atmost k flips
        for (let i = 0; i < N; i++) {
            if (arr[i] == 0)
                cnt++;
 
            while (cnt > K) {
                if (arr[left] == 0)
                    cnt--;
                left++;
            }
            maximum_len1 = Math.max(maximum_len1, i - left + 1);
        }
 
        // Set these variables to 0 for further use
        cnt = 0;
        left = 0;
 
        // Finding length of maximum subarray
        // containing 0's only with atmost k flips
        for (let i = 0; i < N; i++) {
            if (arr[i] == 1)
                cnt++;
 
            while (cnt > K) {
                if (arr[left] == 1)
                    cnt--;
                left++;
            }
            maximum_len0 = Math.max(maximum_len0, i - left + 1);
        }
 
        return Math.max(maximum_len1, maximum_len0);
    }
 
    // Driver code
 
    let arr = [1, 0, 0, 1, 0, 1, 0, 1];
    let K = 2;
    let N = arr.length;
 
    // Function call
    document.write(longestSubSeg(arr, N, K));
 
    // This code is contributed by rakeshsahni
 
</script>

6

Complejidad temporal: O(N)
Espacio auxiliar: O(1)