Minimum length substring with exactly K distinct characters | 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
function findMinLenStr ( str , k ) { var n = str . length ; var st = 0 ; var end = 0 ; var cnt = Array ( 26 ) . fill ( 0 ) ; var distEle = 0 ; var currlen ; var minlen = n ; var startInd = - 1 ; while ( end < n ) { cnt [ str [ end ] . charCodeAt ( 0 ) - ' ' . charCodeAt ( 0 ) ] ++ ; if ( cnt [ str [ end ] . charCodeAt ( 0 ) - ' ' . charCodeAt ( 0 ) ] == 1 ) distEle ++ ; if ( distEle > k ) { while ( st < end && distEle > k ) { if ( cnt [ str [ st ] . charCodeAt ( 0 ) - ' ' . charCodeAt ( 0 ) ] == 1 ) distEle -- ; cnt [ str [ st ] . charCodeAt ( 0 ) - ' ' . charCodeAt ( 0 ) ] -- ; st ++ ; } } if ( distEle == k ) { while ( st < end && cnt [ str [ st ] . charCodeAt ( 0 ) - ' ' . charCodeAt ( 0 ) ] > 1 ) { cnt [ str [ st ] . charCodeAt ( 0 ) - ' ' . charCodeAt ( 0 ) ] -- ; st ++ ; } currlen = end - st + 1 ; if ( currlen < minlen ) { minlen = currlen ; startInd = st ; } } end ++ ; } return str . substr ( startInd , minlen ) ; } var str = " " ; var k = 4 ; document . write ( findMinLenStr ( str , k ) ) ;