Lexicographically smallest permutation of a string that can be reduced to length K by removing K-length prefixes from palindromic substrings of length 2K
Given a binary string str of length N, and an integer K, the task is to find the lexicographically smallest permutation of the string str that can be reduced to length K by removal of every K-length prefix from palindromic substrings of length 2K. If no such permutation exists, print “Not Possible“.
Examples:
Input: str = “0000100001100001”, K = 4
Output: 0001100000011000
Explanation: In the string “0001100000011000”, every 2K length substring becomes a palindrome whenever a K-length prefix is removed, until string length reduces to K.Input: str = “100111”, K = 2
Output: “Not Possible”
Approach: Follow the steps below to solve the problem:
- Count the number of 0s and 1s present in the string. If the count of 0s or 1s is a multiple of N / K, then K reduction of the string is possible. Otherwise, print “Not Possible“.
- Initialize a string tempStr to store the initially formed lexicographically smallest 2K length string.
- Initialize a string finalStr to store the resultant string that satisfies the given conditions.
- Distribute the 0s into a segment of length 2K according to the below formula:
- No of zeroes in 2K length substring, N0 = ((Number of zeroes in N length string)/(Total length of the string))*(2K)
- No of ones in 2K length substring, N1 = (2*K – No of zeroes in 2K length substring)
- Append tempStr with 0s N0/2 times and with 1s N1/2 times and again with 0s N0/2 times.
- Append tempStr (N/2K) times to finalStr and insert (N%2K) characters of the tempStr at the end of the finalStr.
- Print finalStr as the resultant string.
Below is the implementation of the above approach:
C++14
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to count the number of // zeroes present in the string int count_zeroes( int n, string str) { int cnt = 0; // Traverse the string for ( int i = 0; i < str.size(); i++) { if (str[i] == '0' ) cnt++; } // Return the count return cnt; } // Function to rearrange the string s.t // the string can be reduced to a length // K as per the given rules string kReducingStringUtil( int n, int k, string str, int no_of_zeroes) { // Distribute the count of 0s and // 1s in segment of length 2k int zeroes_in_2k = ((no_of_zeroes) * (2 * k)) / n; int ones_in_2k = 2 * k - zeroes_in_2k; // Store string that are initially // have formed lexicographically // smallest 2k length substring 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' ); } // Store the lexicographically // smallest string of length n // that satisfy the condition string final_str = "" ; // Insert temp_str into final_str // (n/2k) times and add (n%2k) // characters of temp_str at end 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 the final string return final_str; } // Function to reduce the string to // length K that follows the given // conditions string kReducingString( int n, int k, string str) { // If the string contains either // 0s or 1s then it always be // reduced into a K length string int no_of_zeroes = count_zeroes(n, str); int no_of_ones = n - no_of_zeroes; // If the string contains only 0s // 1s then it always reduces to // a K length string if (no_of_zeroes == 0 || no_of_zeroes == n) { return str; } // If K = 1 if (k == 1) { if (no_of_zeroes == 0 || no_of_zeroes == n) { return str; } else { return "Not Possible" ; } } // Check whether the given string // is K reducing string or not 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" ; } // Otherwise recursively find // the string return kReducingStringUtil(n, k, str, no_of_zeroes); } // Driver Code int main() { string str = "0000100001100001" ; int K = 4; int N = str.length(); // Function Call cout << kReducingString(N, K, str); return 0; } |
Java
// Java program for the above approach import java.io.*; class GFG{ // Function to count the number of // zeroes present in the string static int count_zeroes( int n, String str) { int cnt = 0 ; // Traverse the string for ( int i = 0 ; i < str.length(); i++) { if (str.charAt(i) == '0' ) cnt++; } // Return the count return cnt; } // Function to rearrange the string s.t // the string can be reduced to a length // K as per the given rules static String kReducingStringUtil( int n, int k, String str, int no_of_zeroes) { // Distribute the count of 0s and // 1s in segment of length 2k int zeroes_in_2k = ((no_of_zeroes) * ( 2 * k)) / n; int ones_in_2k = 2 * k - zeroes_in_2k; // Store string that are initially // have formed lexicographically // smallest 2k length substring String temp_str = "" ; for ( int i = 0 ; i < (zeroes_in_2k) / 2 ; i++) { temp_str += '0' ; } for ( int i = 0 ; i < ones_in_2k; i++) { temp_str += '1' ; } for ( int i = 0 ; i < (zeroes_in_2k) / 2 ; i++) { temp_str += '0' ; } // Store the lexicographically // smallest string of length n // that satisfy the condition String final_str = "" ; // Insert temp_str into final_str // (n/2k) times and add (n%2k) // characters of temp_str at end for ( int i = 0 ; i < n / ( 2 * k); i++) { final_str += (temp_str); } for ( int i = 0 ; i < n % ( 2 * k); i++) { final_str += temp_str.charAt(i); } // Return the final string return final_str; } // Function to reduce the string to // length K that follows the given // conditions static String kReducingString( int n, int k, String str) { // If the string contains either // 0s or 1s then it always be // reduced into a K length string int no_of_zeroes = count_zeroes(n, str); int no_of_ones = n - no_of_zeroes; // If the string contains only 0s // 1s then it always reduces to // a K length string if (no_of_zeroes == 0 || no_of_zeroes == n) { return str; } // If K = 1 if (k == 1 ) { if (no_of_zeroes == 0 || no_of_zeroes == n) { return str; } else { return "Not Possible" ; } } // Check whether the given string // is K reducing string or not boolean check = false ; for ( int i = (n / k); i < n; i += (n / k)) { if (no_of_zeroes == i || no_of_ones == i) { check = true ; break ; } } if (check == false ) { return "Not Possible" ; } // Otherwise recursively find // the string return kReducingStringUtil(n, k, str, no_of_zeroes); } // Driver Code public static void main(String[] args) { String str = "0000100001100001" ; int K = 4 ; int N = str.length(); // Function Call System.out.println(kReducingString(N, K, str)); } } // This code is contributed by akhilsaini |
Python3
# Python3 program for the above approach # Function to count the number of # zeroes present in the string def count_zeroes(n, str ): cnt = 0 # Traverse the string for i in range ( 0 , len ( str )): if ( str [i] = = '0' ): cnt + = 1 # Return the count return cnt # Function to rearrange the string s.t # the string can be reduced to a length # K as per the given rules def kReducingStringUtil(n, k, str , no_of_zeroes): # Distribute the count of 0s and # 1s in segment of length 2k zeroes_in_2k = (((no_of_zeroes) * ( 2 * k)) / / n) ones_in_2k = 2 * k - zeroes_in_2k # Store string that are initially # have formed lexicographically # smallest 2k length substring temp_str = "" for i in range ( 0 , (zeroes_in_2k) / / 2 ): temp_str + = '0' for i in range ( 0 , (ones_in_2k)): temp_str + = '1' for i in range ( 0 , (zeroes_in_2k) / / 2 ): temp_str + = '0' # Store the lexicographically # smallest string of length n # that satisfy the condition final_str = "" # Insert temp_str into final_str # (n/2k) times and add (n%2k) # characters of temp_str at end for i in range ( 0 , n / / ( 2 * k)): final_str + = (temp_str) for i in range ( 0 , n % ( 2 * k)): final_str + = (temp_str[i]) # Return the final string return final_str # Function to reduce the string to # length K that follows the given # conditions def kReducingString(n, k, str ): # If the string contains either # 0s or 1s then it always be # reduced into a K length string no_of_zeroes = count_zeroes(n, str ) no_of_ones = n - no_of_zeroes # If the string contains only 0s # 1s then it always reduces to # a K length string if (no_of_zeroes = = 0 or no_of_zeroes = = n): return str # If K = 1 if (k = = 1 ): if (no_of_zeroes = = 0 or no_of_zeroes = = n): return str else : return "Not Possible" # Check whether the given string # is K reducing string or not check = 0 for i in range ((n / / k), n, (n / / k)): if (no_of_zeroes = = i or no_of_ones = = i): check = 1 break if (check = = 0 ): return "Not Possible" # Otherwise recursively find # the string return kReducingStringUtil(n, k, str , no_of_zeroes) # Driver Code if __name__ = = '__main__' : str = "0000100001100001" K = 4 ; N = len ( str ) # Function Call print (kReducingString(N, K, str )) # This code is contributed by akhilsaini |
C#
// C# program for the above approach using System; class GFG{ // Function to count the number of // zeroes present in the string static int count_zeroes( int n, string str) { int cnt = 0; // Traverse the string for ( int i = 0; i < str.Length; i++) { if (str[i] == '0' ) cnt++; } // Return the count return cnt; } // Function to rearrange the string s.t // the string can be reduced to a length // K as per the given rules static string kReducingStringUtil( int n, int k, string str, int no_of_zeroes) { // Distribute the count of 0s and // 1s in segment of length 2k int zeroes_in_2k = ((no_of_zeroes) * (2 * k)) / n; int ones_in_2k = 2 * k - zeroes_in_2k; // Store string that are initially // have formed lexicographically // smallest 2k length substring string temp_str = "" ; for ( int i = 0; i < (zeroes_in_2k) / 2; i++) { temp_str += '0' ; } for ( int i = 0; i < ones_in_2k; i++) { temp_str += '1' ; } for ( int i = 0; i < (zeroes_in_2k) / 2; i++) { temp_str += '0' ; } // Store the lexicographically // smallest string of length n // that satisfy the condition string final_str = "" ; // Insert temp_str into final_str // (n/2k) times and add (n%2k) // characters of temp_str at end for ( int i = 0; i < n / (2 * k); i++) { final_str += (temp_str); } for ( int i = 0; i < n % (2 * k); i++) { final_str += temp_str[i]; } // Return the final string return final_str; } // Function to reduce the string to // length K that follows the given // conditions static string kReducingString( int n, int k, string str) { // If the string contains either // 0s or 1s then it always be // reduced into a K length string int no_of_zeroes = count_zeroes(n, str); int no_of_ones = n - no_of_zeroes; // If the string contains only 0s // 1s then it always reduces to // a K length string if (no_of_zeroes == 0 || no_of_zeroes == n) { return str; } // If K = 1 if (k == 1) { if (no_of_zeroes == 0 || no_of_zeroes == n) { return str; } else { return "Not Possible" ; } } // Check whether the given string // is K reducing string or not bool check = false ; for ( int i = (n / k); i < n; i += (n / k)) { if (no_of_zeroes == i || no_of_ones == i) { check = true ; break ; } } if (check == false ) { return "Not Possible" ; } // Otherwise recursively find // the string return kReducingStringUtil(n, k, str, no_of_zeroes); } // Driver Code public static void Main() { string str = "0000100001100001" ; int K = 4; int N = str.Length; // Function Call Console.WriteLine(kReducingString(N, K, str)); } } // This code is contributed by akhilsaini |
Javascript
<script> // JavaScript program for the above approach // Function to count the number of // zeroes present in the string function count_zeroes(n, str) { var cnt = 0; // Traverse the string for ( var i = 0; i < str.length; i++) { if (str[i] === "0" ) cnt++; } // Return the count return cnt; } // Function to rearrange the string s.t // the string can be reduced to a length // K as per the given rules function kReducingStringUtil(n, k, str, no_of_zeroes) { // Distribute the count of 0s and // 1s in segment of length 2k var zeroes_in_2k = parseInt((no_of_zeroes * (2 * k)) / n); var ones_in_2k = 2 * k - zeroes_in_2k; // Store string that are initially // have formed lexicographically // smallest 2k length substring var temp_str = "" ; for ( var i = 0; i < zeroes_in_2k / 2; i++) { temp_str += "0" ; } for ( var i = 0; i < ones_in_2k; i++) { temp_str += "1" ; } for ( var i = 0; i < zeroes_in_2k / 2; i++) { temp_str += "0" ; } // Store the lexicographically // smallest string of length n // that satisfy the condition var final_str = "" ; // Insert temp_str into final_str // (n/2k) times and add (n%2k) // characters of temp_str at end 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 the final string return final_str; } // Function to reduce the string to // length K that follows the given // conditions function kReducingString(n, k, str) { // If the string contains either // 0s or 1s then it always be // reduced into a K length string var no_of_zeroes = count_zeroes(n, str); var no_of_ones = n - no_of_zeroes; // If the string contains only 0s // 1s then it always reduces to // a K length string if (no_of_zeroes === 0 || no_of_zeroes === n) { return str; } // If K = 1 if (k === 1) { if (no_of_zeroes === 0 || no_of_zeroes === n) { return str; } else { return "Not Possible" ; } } // Check whether the given string // is K reducing string or not 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 "Not Possible" ; } // Otherwise recursively find // the string return kReducingStringUtil(n, k, str, no_of_zeroes); } // Driver Code var str = "0000100001100001" ; var K = 4; var N = str.length; // Function Call document.write(kReducingString(N, K, str)); </script> |
Output:
0001100000011000
Time Complexity: O(N)
Auxiliary Space: O(1)