Longest subarray not having more than K 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 Code
import collections NEW_LINE def longest ( a , n , k ) : NEW_LINE INDENT freq = collections . defaultdict ( int ) NEW_LINE start = 0 NEW_LINE end = 0 NEW_LINE now = 0 NEW_LINE l = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT freq [ a [ i ] ] += 1 NEW_LINE if ( freq [ a [ i ] ] == 1 ) : NEW_LINE INDENT now += 1 NEW_LINE DEDENT while ( now > k ) : NEW_LINE INDENT freq [ a [ l ] ] -= 1 NEW_LINE if ( freq [ a [ l ] ] == 0 ) : NEW_LINE INDENT now -= 1 NEW_LINE DEDENT l += 1 NEW_LINE DEDENT if ( i - l + 1 >= end - start + 1 ) : NEW_LINE INDENT end = i NEW_LINE start = l NEW_LINE DEDENT DEDENT for i in range ( start , end + 1 ) : NEW_LINE INDENT print ( a [ i ] , end = " ▁ " ) NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT a = [ 6 , 5 , 1 , 2 , 3 , 2 , 1 , 4 , 5 ] NEW_LINE n = len ( a ) NEW_LINE k = 3 NEW_LINE longest ( a , n , k ) NEW_LINE DEDENT