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
def findMinLenStr ( str , k ) : NEW_LINE INDENT n = len ( str ) NEW_LINE st = 0 NEW_LINE end = 0 NEW_LINE cnt = [ 0 ] * 26 NEW_LINE distEle = 0 NEW_LINE currlen = 0 NEW_LINE minlen = n NEW_LINE startInd = - 1 NEW_LINE while ( end < n ) : NEW_LINE INDENT cnt [ ord ( str [ end ] ) - ord ( ' a ' ) ] += 1 NEW_LINE if ( cnt [ ord ( str [ end ] ) - ord ( ' a ' ) ] == 1 ) : NEW_LINE INDENT distEle += 1 NEW_LINE DEDENT if ( distEle > k ) : NEW_LINE INDENT while ( st < end and distEle > k ) : NEW_LINE INDENT if ( cnt [ ord ( str [ st ] ) - ord ( ' a ' ) ] == 1 ) : NEW_LINE INDENT distEle -= 1 NEW_LINE DEDENT cnt [ ord ( str [ st ] ) - ord ( ' a ' ) ] -= 1 NEW_LINE st += 1 NEW_LINE DEDENT DEDENT if ( distEle == k ) : NEW_LINE INDENT while ( st < end and cnt [ ord ( str [ st ] ) - ord ( ' a ' ) ] > 1 ) : NEW_LINE INDENT cnt [ ord ( str [ st ] ) - ord ( ' a ' ) ] -= 1 NEW_LINE st += 1 NEW_LINE DEDENT currlen = end - st + 1 NEW_LINE if ( currlen < minlen ) : NEW_LINE INDENT minlen = currlen NEW_LINE startInd = st NEW_LINE DEDENT DEDENT end += 1 NEW_LINE DEDENT return str [ startInd : startInd + minlen ] NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT str = " efecfefd " NEW_LINE k = 4 NEW_LINE print ( findMinLenStr ( str , k ) ) NEW_LINE DEDENT