Minimum length substring with exactly K distinct characters | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; string findMinLenStr ( string str , int k ) { int n = str . length ( ) ; int st = 0 ; int end = 0 ; int cnt [ 26 ] ; memset ( cnt , 0 , sizeof ( cnt ) ) ; int distEle = 0 ; int currlen ; int minlen = n ; int startInd = -1 ; while ( end < n ) { cnt [ str [ end ] - ' a ' ] ++ ; if ( cnt [ str [ end ] - ' a ' ] == 1 ) distEle ++ ; if ( distEle > k ) { while ( st < end && distEle > k ) { if ( cnt [ str [ st ] - ' a ' ] == 1 ) distEle -- ; cnt [ str [ st ] - ' a ' ] -- ; st ++ ; } } if ( distEle == k ) { while ( st < end && cnt [ str [ st ] - ' a ' ] > 1 ) { cnt [ str [ st ] - ' a ' ] -- ; st ++ ; } currlen = end - st + 1 ; if ( currlen < minlen ) { minlen = currlen ; startInd = st ; } } end ++ ; } return str . substr ( startInd , minlen ) ; } int main ( ) { string str = " efecfefd " ; int k = 4 ; cout << findMinLenStr ( str , k ) ; return 0 ; }