Encuentre la longitud del subarreglo más largo con al menos K ocurrencias del entero X

Dados dos números K, X y un arreglo arr[] que contiene N enteros, la tarea es encontrar la longitud del subarreglo más largo tal que contenga como máximo ‘K’ ocurrencias del entero ‘X’.
Ejemplos: 
 

Entrada: K = 2, X = 2, arr[] = {1, 2, 2, 3, 4} 
Salida: 5 
Explicación: 
El subarreglo más largo es {1, 2, 2, 3, 4} que es el array completa ya que contiene como máximo ‘2’ ocurrencias del elemento ‘2’.
Entrada: K = 1, X = 2, arr[] = {1, 2, 2, 3, 4}, 
Salida: 3 
Explicación: 
El subarreglo más largo es {2, 3, 4} ya que contiene como máximo ‘1’ ocurrencia del elemento ‘2’. 
 

Enfoque ingenuo: el enfoque ingenuo para este problema es generar todos los subarreglos posibles para el subarreglo dado. Luego, para cada subarreglo , encuentre el subarreglo más grande que contenga como máximo K ocurrencias del elemento X. La complejidad de tiempo para este enfoque es O(N ² ) donde N es el número de elementos en la array. 
Enfoque eficiente: la idea para resolver este problema es utilizar la técnica  de dos punteros .
 

• Inicialice dos punteros ‘i’ y ‘j’ a -1 y 0 respectivamente.
• Siga incrementando ‘i’. Si se encuentra un elemento X, aumente la cuenta de ese elemento manteniendo un contador.
• Si el conteo de X se vuelve mayor que K, entonces disminuya el conteo y también disminuya el valor de ‘j’.
• Si el recuento de X se vuelve menor o igual que K, incremente ‘i’ y no realice cambios en ‘j’.
• Los índices ‘i’ y ‘j’ aquí representan el punto inicial y el punto final del subarreglo que se está considerando.
• Por lo tanto, en cada paso, encuentra el valor de |i – j + 1|. El valor máximo posible para esto es la respuesta requerida.

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

// C++ program to find the length of the
// longest subarray which contains at-most
// K occurrences of the integer X
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the length of the
// longest subarray  which contains at-most
// K occurrences of the integer X
int longest(int a[], int n, int k, int x)
{
    // Maximum initialized to zero
    int max = 0;
 
    // Both the pointers initialized to -1
    int i = -1;
    int j = 0;
 
    // Variable to store the count of the
    // occurrence of the element 'x'
    int m1 = 0;
 
    // Iterate through the array once
    while (i < n) {
 
        // If the count is less than equal to K
        if (m1 <= k) {
 
            // Then increase 'i'
            i++;
            if (a[i] == x) {
 
                // If the integer 'x' is found,
                // increase the count.
                m1++;
            }
        }
 
        // If the count is greater than K
        else {
 
            // If the element 'x' is found,
            // then decrease the count
            if (a[j] == x) {
                m1--;
            }
 
            // Increment the value of j.
            // This signifies that we are looking
            // at another subarray
            j++;
        }
 
// Find the maximum possible value
// among the obtained values
        if (m1 <= k && i < n) {
 
            if (abs(i - j + 1) > max) {
                max = abs(i - j + 1);
            }
        }
 
         
    }
 
    return max;
}
 
// Driver code
int main()
{
    int arr[] = { 1, 2, 2, 3, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;
    int x = 2;
 
    cout << longest(arr, n, k, x);
 
    return 0;
}

// Java program to find the length of the
// longest subarray which contains at-most
// K occurrences of the integer X
import java.util.*;
 
class GFG{
 
// Function to find the length of the
// longest subarray which contains at-most
// K occurrences of the integer X
static int longest(int a[], int n,
                   int k, int x)
{
 
    // Maximum initialized to zero
    int max = 0;
 
    // Both the pointers initialized to -1
    int i = -1;
    int j = 0;
 
    // Variable to store the count of the
    // occurrence of the element 'x'
    int m1 = 0;
 
    // Iterate through the array once
    while (i < n)
    {
 
        // If the count is less
        // than equal to K
        if (m1 <= k)
        {
 
            // Then increase 'i'
            i++;
 
            if (i < a.length && a[i] == x)
            {
 
                // If the integer 'x' is
                // found, increase the count.
                m1++;
            }
        }
 
        // If the count is greater than K
        else
        {
 
            // If the element 'x' is found,
            // then decrease the count
            if (j < a.length && a[j] == x)
            {
                m1--;
            }
 
            // Increment the value of j.
            // This signifies that we are
            // looking at another subarray
            j++;
        }
         
        // Find the maximum possible value
        // among the obtained values
        if (m1 <= k && i < n)
        {
            if (Math.abs(i - j + 1) > max)
            {
                max = Math.abs(i - j + 1);
            }
        }
    }
 
    return max;
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = { 1, 2, 2, 3, 4 };
    int n = arr.length;
    int k = 2;
    int x = 2;
 
    System.out.print(longest(arr, n, k, x));
}
}
 
// This code is contributed by Amit Katiyar

# Python3 program to find the length of the
# longest subarray which contains at-most
# K occurrences of the integer X
 
# Function to find the length of the
# longest subarray which contains at-most
# K occurrences of the integer X
def longest(a, n, k, x):
     
    # Maximum initialized to zero
    max = 0;
 
    # Both the pointers initialized to -1
    i = -1;
    j = 0;
 
    # Variable to store the count of the
    # occurrence of the element 'x'
    m1 = 0;
 
    # Iterate through the array once
    while (i < n):
 
        # If the count is less than equal to K
        if (m1 <= k):
            if (a[i] == x):
 
                # If the integer 'x' is found,
                # increase the count.
                m1 += 1;
                 
            # Then increase 'i'    
            i += 1;
 
        # If the count is greater than K
        else :
 
            # If the element 'x' is found,
            # then decrease the count
            if (a[j] == x):
                m1 -= 1;
 
            # Increment the value of j.
            # This signifies that we are looking
            # at another subarray
            j += 1;
         
        # Find the maximum possible value
        # among the obtained values
        if (m1 <= k and i < n):
            if (abs(i - j + 1) > max):
                max = abs(i - j + 1);
             
    return max;
 
# Driver code
if __name__ == "__main__" :
 
    arr = [ 1, 2, 2, 3, 4 ];
    n = len(arr);
    k = 2;
    x = 2;
     
    print(longest(arr, n, k, x));
 
# This code is contributed by AnkitRai01

// C# program to find the length of the
// longest subarray which contains at-most
// K occurrences of the integer X
using System;
 
class GFG{
 
// Function to find the length of the
// longest subarray which contains at-most
// K occurrences of the integer X
static int longest(int []a, int n,
                   int k, int x)
{
     
    // Maximum initialized to zero
    int max = 0;
     
    // Both the pointers initialized to -1
    int i = -1;
    int j = 0;
     
    // Variable to store the count of the
    // occurrence of the element 'x'
    int m1 = 0;
     
    // Iterate through the array once
    while (i < n)
    {
     
        // If the count is less
        // than equal to K
        if (m1 <= k)
        {
     
            // Then increase 'i'
            i++;
             
            if (i < a.Length && a[i] == x)
            {
     
                // If the integer 'x' is
                // found, increase the count.
                m1++;
            }
        }
     
        // If the count is greater than K
        else
        {
     
            // If the element 'x' is found,
            // then decrease the count
            if (j < a.Length && a[j] == x)
            {
                m1--;
            }
     
            // Increment the value of j.
            // This signifies that we are
            // looking at another subarray
            j++;
        }
             
        // Find the maximum possible value
        // among the obtained values
        if (m1 <= k && i < n)
        {
            if (Math.Abs(i - j + 1) > max)
            {
                max = Math.Abs(i - j + 1);
            }
        }
    }
     
    return max;
}
     
// Driver code
public static void Main(string[] args)
{
    int []arr = { 1, 2, 2, 3, 4 };
    int n = arr.Length;
    int k = 2;
    int x = 2;
     
    Console.WriteLine(longest(arr, n, k, x));
}
}
 
// This code is contributed by AnkitRai01

<script>
 
// javascript program to find the length of the
// longest subarray which contains at-most
// K occurrences of the integer X
 
    // Function to find the length of the
    // longest subarray which contains at-most
    // K occurrences of the integer X
    function longest( a , n , k , x) {
 
        // Maximum initialized to zero
        var max = 0;
 
        // Both the pointers initialized to -1
        var i = -1;
        var j = 0;
 
        // Variable to store the count of the
        // occurrence of the element 'x'
        var m1 = 0;
 
        // Iterate through the array once
        while (i < n) {
 
            // If the count is less
            // than equal to K
            if (m1 <= k) {
 
                // Then increase 'i'
                i++;
 
                if (i < a.length && a[i] == x) {
 
                    // If the integer 'x' is
                    // found, increase the count.
                    m1++;
                }
            }
 
            // If the count is greater than K
            else {
 
                // If the element 'x' is found,
                // then decrease the count
                if (j < a.length && a[j] == x) {
                    m1--;
                }
 
                // Increment the value of j.
                // This signifies that we are
                // looking at another subarray
                j++;
            }
 
            // Find the maximum possible value
            // among the obtained values
            if (m1 <= k && i < n) {
                if (Math.abs(i - j + 1) > max) {
                    max = Math.abs(i - j + 1);
                }
            }
        }
 
        return max;
    }
 
    // Driver code
     
        var arr = [ 1, 2, 2, 3, 4 ];
        var n = arr.length;
        var k = 2;
        var x = 2;
 
        document.write(longest(arr, n, k, x));
 
// This code contributed by Princi Singh
</script>

5

Complejidad de tiempo: O(N) , donde N es la longitud de la array.