text: Longest subarray not having more than K distinct elements | CPP program to find longest subarray with k or less distinct elements . ; function to print the longest sub - array ; mark the element visited ; if its visited first time , then increase the counter of distinct elements by 1 ; When the counter of distinct elements increases from k , then reduce it to k ; from the left , reduce the number of time of visit ; if the reduced visited time element is not present in further segment then decrease the count of distinct elements ; increase the subsegment mark ; check length of longest sub - segment when greater then previous best then change it ; print the longest sub - segment ; driver program to test the above function
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; 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 ++ ) { freq [ a [ i ] ] ++ ; if ( freq [ a [ i ] ] == 1 ) now ++ ; while ( now > k ) { freq [ a [ l ] ] -- ; if ( freq [ a [ l ] ] == 0 ) now -- ; l ++ ; } if ( i - l + 1 >= end - start + 1 ) end = i , start = l ; } for ( int i = start ; i <= end ; i ++ ) cout << a [ i ] << " ▁ " ; } 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 ; }