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
function count_zeroes ( n , str ) { var cnt = 0 ; for ( var i = 0 ; i < str . length ; i ++ ) { if ( str [ i ] === " " ) cnt ++ ; } return cnt ; } function kReducingStringUtil ( n , k , str , no_of_zeroes ) { var zeroes_in_2k = parseInt ( ( no_of_zeroes * ( 2 * k ) ) / n ) ; var ones_in_2k = 2 * k - zeroes_in_2k ; var temp_str = " " ; for ( var i = 0 ; i < zeroes_in_2k / 2 ; i ++ ) { temp_str += " " ; } for ( var i = 0 ; i < ones_in_2k ; i ++ ) { temp_str += " " ; } for ( var i = 0 ; i < zeroes_in_2k / 2 ; i ++ ) { temp_str += " " ; } var final_str = " " ; for ( var i = 0 ; i < n / ( 2 * k ) ; i ++ ) { final_str += temp_str ; } for ( var i = 0 ; i < n % ( 2 * k ) ; i ++ ) { final_str += temp_str [ i ] ; } return final_str ; } function kReducingString ( n , k , str ) { var no_of_zeroes = count_zeroes ( n , str ) ; var no_of_ones = n - no_of_zeroes ; if ( no_of_zeroes === 0 no_of_zeroes === n ) { return str ; } if ( k === 1 ) { if ( no_of_zeroes === 0 no_of_zeroes === n ) { return str ; } else { return " " ; } } var check = false ; for ( var i = n / k ; i < n ; i += n / k ) { if ( no_of_zeroes === i no_of_ones === i ) { check = true ; break ; } } if ( check === false ) { return " " ; } return kReducingStringUtil ( n , k , str , no_of_zeroes ) ; } var str = " " ; var K = 4 ; var N = str . length ; document . write ( kReducingString ( N , K , str ) ) ;