Minimum length substring with exactly K distinct characters | Java program to find minimum length subString having exactly k distinct character . ; Function to find minimum length subString having exactly k distinct character . ; Starting index of sliding window . ; Ending index of sliding window . ; To store count of character . ; To store count of distinct character in current sliding window . ; To store length of current sliding window . ; To store minimum length . ; To store starting index of minimum length subString . ; Increment count of current character If this count is one then a new distinct character is found in sliding window . ; If number of distinct characters is is greater than k , then move starting point of sliding window forward , until count is k . ; Remove characters from the beginning of sliding window having count more than 1 to minimize length . ; Compare length with minimum length and update if required . ; Return minimum length subString . ; Driver code
class GFG { static String findMinLenStr ( String str , int k ) { int n = str . length ( ) ; int st = 0 ; int end = 0 ; int cnt [ ] = new int [ 26 ] ; for ( int i = 0 ; i < 26 ; i ++ ) cnt [ i ] = 0 ; int distEle = 0 ; int currlen ; int minlen = n ; int startInd = - 1 ; while ( end < n ) { cnt [ str . charAt ( end ) - ' a ' ] ++ ; if ( cnt [ str . charAt ( end ) - ' a ' ] == 1 ) distEle ++ ; if ( distEle > k ) { while ( st < end && distEle > k ) { if ( cnt [ str . charAt ( st ) - ' a ' ] == 1 ) distEle -- ; cnt [ str . charAt ( st ) - ' a ' ] -- ; st ++ ; } } if ( distEle == k ) { while ( st < end && cnt [ str . charAt ( st ) - ' a ' ] > 1 ) { cnt [ str . charAt ( st ) - ' a ' ] -- ; st ++ ; } currlen = end - st + 1 ; if ( currlen < minlen ) { minlen = currlen ; startInd = st ; } } end ++ ; } return str . substring ( startInd , startInd + minlen ) ; } public static void main ( String args [ ] ) { String str = " efecfefd " ; int k = 4 ; System . out . println ( findMinLenStr ( str , k ) ) ; } }