El subarreglo más largo que no tiene más de K elementos distintos

Dados N elementos y un número K, encuentre el subarreglo más largo que no tenga más de K elementos distintos (puede tener menos de K).

Ejemplos: 

Input : arr[] = {1, 2, 3, 4, 5}
            k = 6 
Output : 1 2 3 4 5 
Explanation: The whole array has only 5 
distinct elements which is less than k, 
so we print the array itself.

Input: arr[] = {6, 5, 1, 2, 3, 2, 1, 4, 5}
           k = 3
Output: 1 2 3 2 1, 
The output is the longest subarray with 3
distinct elements.

Un enfoque ingenuo será atravesar la array y usar hashing para cada sub-arrays, y verificar la sub-array más larga posible con no más de K elementos distintos. 

Un enfoque eficiente es usar el concepto de dos punteros donde mantenemos un hash para contar las ocurrencias de elementos. Comenzamos desde el principio y mantenemos un conteo de elementos distintos hasta que el número exceda k. Una vez que excede K, comenzamos a disminuir el conteo de los elementos en el hash desde donde comenzó el subarreglo y reducimos nuestra longitud a medida que los subarreglos disminuyen para que el puntero se mueva hacia la derecha. Seguimos eliminando elementos hasta que nuevamente obtenemos k elementos distintos. Continuamos este proceso hasta que nuevamente tengamos más de k elementos distintos y mantenemos el puntero izquierdo constante hasta entonces. Actualizamos nuestro inicio y fin de acuerdo con eso si la nueva longitud del subarreglo es mayor que la anterior. 

Implementación:

// CPP program to find longest subarray with
// k or less distinct elements.
#include <bits/stdc++.h>
using namespace std;
 
// function to print the longest sub-array
void longest(int a[], int n, int k)
{
    unordered_map<int, int> freq;
 
    int start = 0, end = 0, now = 0, l = 0;
    for (int i = 0; i < n; i++) {
 
        // mark the element visited
        freq[a[i]]++;
 
        // if its visited first time, then increase
        // the counter of distinct elements by 1
        if (freq[a[i]] == 1)
            now++;
 
        // When the counter of distinct elements
        // increases from k, then reduce it to k
        while (now > k) {
 
            // from the left, reduce the number of
            // time of visit
            freq[a[l]]--;
 
            // if the reduced visited time element
            // is not present in further segment
            // then decrease the count of distinct
            // elements
            if (freq[a[l]] == 0)
                now--;
 
            // increase the subsegment mark
            l++;
        }
 
        // check length of longest sub-segment
        // when greater than previous best
        // then change it
        if (i - l + 1 >= end - start + 1)
            end = i, start = l;
    }
 
    // print the longest sub-segment
    for (int i = start; i <= end; i++)
        cout << a[i] << " ";
}
 
// driver program to test the above function
int main()
{
    int a[] = { 6, 5, 1, 2, 3, 2, 1, 4, 5 };
    int n = sizeof(a) / sizeof(a[0]);
    int k = 3;
    longest(a, n, k);
    return 0;
}

// Java program to find longest subarray with
// k or less distinct elements.
import java.util.*;
 
class GFG
{
 
// function to print the longest sub-array
static void longest(int a[], int n, int k)
{
    int[] freq = new int[7];
 
    int start = 0, end = 0, now = 0, l = 0;
    for (int i = 0; i < n; i++)
    {
 
        // mark the element visited
        freq[a[i]]++;
 
        // if its visited first time, then increase
        // the counter of distinct elements by 1
        if (freq[a[i]] == 1)
            now++;
 
        // When the counter of distinct elements
        // increases from k, then reduce it to k
        while (now > k)
        {
 
            // from the left, reduce the number of
            // time of visit
            freq[a[l]]--;
 
            // if the reduced visited time element
            // is not present in further segment
            // then decrease the count of distinct
            // elements
            if (freq[a[l]] == 0)
                now--;
 
            // increase the subsegment mark
            l++;
        }
 
        // check length of longest sub-segment
        // when greater than previous best
        // then change it
        if (i - l + 1 >= end - start + 1)
        {
            end = i;
            start = l;
        }
    }
 
    // print the longest sub-segment
    for (int i = start; i <= end; i++)
        System.out.print(a[i]+" ");
}
 
// Driver code
public static void main(String args[])
{
    int a[] = { 6, 5, 1, 2, 3, 2, 1, 4, 5 };
    int n = a.length;
    int k = 3;
    longest(a, n, k);
}
}
 
// This code is contributed by
// Surendra_Gangwar

# Python 3 program to find longest
# subarray with k or less distinct elements.
 
# function to print the longest sub-array
import collections
def longest(a, n, k):
 
    freq = collections.defaultdict(int)
 
    start = 0
    end = 0
    now = 0
    l = 0
    for i in range(n):
 
        # mark the element visited
        freq[a[i]] += 1
 
        # if its visited first time, then increase
        # the counter of distinct elements by 1
        if (freq[a[i]] == 1):
            now += 1
 
        # When the counter of distinct elements
        # increases from k, then reduce it to k
        while (now > k) :
 
            # from the left, reduce the number
            # of time of visit
            freq[a[l]] -= 1
 
            # if the reduced visited time element
            # is not present in further segment
            # then decrease the count of distinct
            # elements
            if (freq[a[l]] == 0):
                now -= 1
 
            # increase the subsegment mark
            l += 1
 
        # check length of longest sub-segment
        # when greater than previous best
        # then change it
        if (i - l + 1 >= end - start + 1):
            end = i
            start = l
 
    # print the longest sub-segment
    for i in range(start, end + 1):
        print(a[i], end = " ")
 
# Driver Code
if __name__ == "__main__":
 
    a = [ 6, 5, 1, 2, 3,
             2, 1, 4, 5 ]
    n = len(a)
    k = 3
    longest(a, n, k)
 
# This code is contributed
# by ChitraNayal

// C# program to find longest subarray with
// k or less distinct elements.
using System;
     
class GFG
{
 
// function to print the longest sub-array
static void longest(int []a, int n, int k)
{
    int[] freq = new int[7];
 
    int start = 0, end = 0, now = 0, l = 0;
    for (int i = 0; i < n; i++)
    {
 
        // mark the element visited
        freq[a[i]]++;
 
        // if its visited first time, then increase
        // the counter of distinct elements by 1
        if (freq[a[i]] == 1)
            now++;
 
        // When the counter of distinct elements
        // increases from k, then reduce it to k
        while (now > k)
        {
 
            // from the left, reduce the number of
            // time of visit
            freq[a[l]]--;
 
            // if the reduced visited time element
            // is not present in further segment
            // then decrease the count of distinct
            // elements
            if (freq[a[l]] == 0)
                now--;
 
            // increase the subsegment mark
            l++;
        }
 
        // check length of longest sub-segment
        // when greater than previous best
        // then change it
        if (i - l + 1 >= end - start + 1)
        {
            end = i;
            start = l;
        }
    }
 
    // print the longest sub-segment
    for (int i = start; i <= end; i++)
        Console.Write(a[i]+" ");
}
 
// Driver code
public static void Main(String []args)
{
    int []a = { 6, 5, 1, 2, 3, 2, 1, 4, 5 };
    int n = a.Length;
    int k = 3;
    longest(a, n, k);
}
}
 
// This code contributed by Rajput-Ji

<script>
 
// JavaScript program to find longest subarray with
// k or less distinct elements.
 
// function to print the longest sub-array
function longest(a, n, k)
{
    var freq = Array(7).fill(0);
 
    var start = 0, end = 0, now = 0, l = 0;
    for (var i = 0; i < n; i++)
    {
 
        // mark the element visited
        freq[a[i]]++;
 
        // if its visited first time, then increase
        // the counter of distinct elements by 1
        if (freq[a[i]] == 1)
            now++;
 
        // When the counter of distinct elements
        // increases from k, then reduce it to k
        while (now > k)
        {
 
            // from the left, reduce the number of
            // time of visit
            freq[a[l]]--;
 
            // if the reduced visited time element
            // is not present in further segment
            // then decrease the count of distinct
            // elements
            if (freq[a[l]] == 0)
                now--;
 
            // increase the subsegment mark
            l++;
        }
 
        // check length of longest sub-segment
        // when greater than previous best
        // then change it
        if (i - l + 1 >= end - start + 1)
        {
            end = i;
            start = l;
        }
    }
 
    // print the longest sub-segment
    for (var i = start; i <= end; i++)
        document.write(a[i]+" ");
}
 
// driver program to test the above function
var a = [6, 5, 1, 2, 3, 2, 1, 4, 5];
var n = a.length;
var k = 3;
longest(a, n, k);
 
</script>

1 2 3 2 1 

Complejidad de tiempo: O (N), ya que estamos usando un bucle para atravesar N veces.
Espacio auxiliar: O (N), ya que estamos usando espacio adicional para la array de frecuencias.

Este artículo es una contribución de Striver . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.