Lexicographically smallest permutation of a string that can be reduced to length K by removing K | C ++ program for the above approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int count_zeroes ( int n , string str ) { int cnt = 0 ; for ( int i = 0 ; i < str . size ( ) ; i ++ ) { if ( str [ i ] == '0' ) cnt ++ ; } return cnt ; } string kReducingStringUtil ( int n , int k , string str , int no_of_zeroes ) { int zeroes_in_2k = ( ( no_of_zeroes ) * ( 2 * k ) ) / n ; int ones_in_2k = 2 * k - zeroes_in_2k ; string temp_str = " " ; for ( int i = 0 ; i < ( zeroes_in_2k ) / 2 ; i ++ ) { temp_str . push_back ( '0' ) ; } for ( int i = 0 ; i < ones_in_2k ; i ++ ) { temp_str . push_back ( '1' ) ; } for ( int i = 0 ; i < ( zeroes_in_2k ) / 2 ; i ++ ) { temp_str . push_back ( '0' ) ; } string final_str = " " ; for ( int i = 0 ; i < n / ( 2 * k ) ; i ++ ) { final_str += ( temp_str ) ; } for ( int i = 0 ; i < n % ( 2 * k ) ; i ++ ) { final_str . push_back ( temp_str [ i ] ) ; } return final_str ; } string kReducingString ( int n , int k , string str ) { int no_of_zeroes = count_zeroes ( n , str ) ; int 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 " Not ▁ Possible " ; } } bool check = 0 ; for ( int i = ( n / k ) ; i < n ; i += ( n / k ) ) { if ( no_of_zeroes == i no_of_ones == i ) { check = 1 ; break ; } } if ( check == 0 ) { return " Not ▁ Possible " ; } return kReducingStringUtil ( n , k , str , no_of_zeroes ) ; } int main ( ) { string str = "0000100001100001" ; int K = 4 ; int N = str . length ( ) ; cout << kReducingString ( N , K , str ) ; return 0 ; }