Lexicographically smallest permutation of a string that can be reduced to length K by removing K | Function to count the number of zeroes present in the string ; Traverse the string ; Return the count ; Function to rearrange the string s . t the string can be reduced to a length K as per the given rules ; Distribute the count of 0 s and 1 s in segment of length 2 k ; Store string that are initially have formed lexicographically smallest 2 k length substring ; Store the lexicographically smallest string of length n that satisfy the condition ; Insert temp_str into final_str ( n / 2 k ) times and add ( n % 2 k ) characters of temp_str at end ; Return the final string ; Function to reduce the string to length K that follows the given conditions ; If the string contains either 0 s or 1 s then it always be reduced into a K length string ; If the string contains only 0 s 1 s then it always reduces to a K length string ; If K = 1 ; Check whether the given string is K reducing string or not ; Otherwise recursively find the string ; Driver Code ; Function Call
def count_zeroes ( n , str ) : NEW_LINE INDENT cnt = 0 NEW_LINE for i in range ( 0 , len ( str ) ) : NEW_LINE INDENT if ( str [ i ] == '0' ) : NEW_LINE cnt += 1 NEW_LINE DEDENT return cnt NEW_LINE DEDENT def kReducingStringUtil ( n , k , str , no_of_zeroes ) : NEW_LINE INDENT zeroes_in_2k = ( ( ( no_of_zeroes ) * ( 2 * k ) ) // n ) NEW_LINE ones_in_2k = 2 * k - zeroes_in_2k NEW_LINE temp_str = " " NEW_LINE for i in range ( 0 , ( zeroes_in_2k ) // 2 ) : NEW_LINE INDENT temp_str += '0' NEW_LINE DEDENT for i in range ( 0 , ( ones_in_2k ) ) : NEW_LINE INDENT temp_str += '1' NEW_LINE DEDENT for i in range ( 0 , ( zeroes_in_2k ) // 2 ) : NEW_LINE INDENT temp_str += '0' NEW_LINE DEDENT final_str = " " NEW_LINE for i in range ( 0 , n // ( 2 * k ) ) : NEW_LINE INDENT final_str += ( temp_str ) NEW_LINE DEDENT for i in range ( 0 , n % ( 2 * k ) ) : NEW_LINE INDENT final_str += ( temp_str [ i ] ) NEW_LINE DEDENT return final_str NEW_LINE DEDENT def kReducingString ( n , k , str ) : NEW_LINE INDENT no_of_zeroes = count_zeroes ( n , str ) NEW_LINE no_of_ones = n - no_of_zeroes NEW_LINE if ( no_of_zeroes == 0 or no_of_zeroes == n ) : NEW_LINE INDENT return str NEW_LINE DEDENT if ( k == 1 ) : NEW_LINE INDENT if ( no_of_zeroes == 0 or no_of_zeroes == n ) : NEW_LINE return str NEW_LINE else : NEW_LINE return " Not ▁ Possible " NEW_LINE DEDENT check = 0 NEW_LINE for i in range ( ( n // k ) , n , ( n // k ) ) : NEW_LINE INDENT if ( no_of_zeroes == i or no_of_ones == i ) : NEW_LINE check = 1 NEW_LINE break NEW_LINE DEDENT if ( check == 0 ) : NEW_LINE INDENT return " Not ▁ Possible " NEW_LINE DEDENT return kReducingStringUtil ( n , k , str , no_of_zeroes ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT str = "0000100001100001" NEW_LINE K = 4 ; NEW_LINE N = len ( str ) NEW_LINE print ( kReducingString ( N , K , str ) ) NEW_LINE DEDENT