Generate N sized binary string with prefix S and is lexicographically smallest possible
Given a binary string S, the task is to make a binary string of size N from the given string S (don’t change the position of characters) following the below conditions:
- The prefix of the string is S.
- If is the lexicographically smallest possible.
- Absolute difference between the number of 1s and 0s is minimum.
Examples:
Input: S = “101”, N = 8
Output: 10100011
Explanation: The prefix of output string is same as the string S.
The absolute difference between number of 0s and 1s is 0.
It is the lexicographically smallest possible which follows all the given condition.Input: S = “001”, N = 7
Output: 0010011
Approach: This problem can be solved by using the Greedy Approach based on the following idea:
In the case of a binary string, a string starting with ‘0’ is lexicographically smaller than the one starting with ‘1‘.
So, firstly make S the prefix and then find how many more 0s and 1s can be added. To make it lexicographically smallest, add all the 0s first and then the 1s.
Follow the steps mentioned below to implement the approach.
- Count numbers of 1’s and 0’s and store them (say in count1 and count0 respectively).
- Find the difference between (say g) count0 and count1 and between N and length of S (say in a variable l).
- Calculate the size which we need to increment in string length to make string length = N and store it in l.
- Now add as many 0s (which will be (l-g)/2) such that the number of 0 becomes the same as N/2 and then add 1s for the remaining places.
Below is the implementation of the above approach:
C++
#include <iostream> using namespace std; // Function to build string string find_string( int n, string s) { // Declaring variable int count0 = 0, count1 = 0; // Check number of 1's and 0's for ( int i = 0; i < s.length(); i++) { if (s[i] == '0' ) { count0++; } else { count1++; } } string sb = s; // Store difference in number of 1's // and 0's int g = count0 - count1; // l store the value that how much 0's // or 1's we need to add in string int l = n - s.length(); l -= g; // u store the count of // number of 0's we need to insert int u = l / 2; while (u > 0) { sb += '0' ; u--; } if (l % 2 != 0) { sb += '0' ; } while (sb.length() < n) { sb += '1' ; } // Return result return sb; } // Driver code int main() { int N = 7; string S = "001" ; // Function call cout << find_string(N, S); } // This code is contributed by phasing17 |
Java
// Java program for above approach import java.io.*; import java.lang.*; class GFG { // Function to build string String find_string( int n, String s) { // Declaring variable int count0 = 0 , count1 = 0 ; // Check number of 1's and 0's for ( int i = 0 ; i < s.length(); i++) { if (s.charAt(i) == '0' ) { count0++; } else { count1++; } } String sb = s; // Store difference in number of 1's // and 0's int g = count0 - count1; // l store the value that how much 0's // or 1's we need to add in string int l = n - s.length(); l -= g; // u store the count of // number of 0's we need to insert int u = l / 2 ; while (u > 0 ) { sb += '0' ; u--; } if (l % 2 != 0 ) { sb += '0' ; } while (sb.length() < n) { sb += '1' ; } // Return result return sb; } // Driver code public static void main(String[] args) { int N = 7 ; String S = "001" ; GFG g = new GFG(); // Function call System.out.println(g.find_string(N, S)); } } |
Python3
# Python program for above approach # Function to build string def find_string(n, s): # Declaring variable count0 = 0 count1 = 0 # Check number of 1's and 0's for i in range ( len (s)): if (s[i] = = '0' ): count0 + = 1 else : count1 + = 1 sb = s # Store difference in number of 1's # and 0's g = count0 - count1 # l store the value that how much 0's # or 1's we need to add in string l = n - len (s) l - = g # u store the count of # number of 0's we need to insert u = l / / 2 while (u > 0 ): sb + = '0' u - = 1 if (l % 2 ! = 0 ): sb + = '0' while ( len (sb) < n): sb + = '1' # Return result return sb # Driver Code N = 7 S = "001" # Function call print (find_string(N, S)) # This code is contributed by shinjanpatra |
C#
// C# code to implement the above approach using System; class GFG { // Function to build string string find_string( int n, string s) { // Declaring variable int count0 = 0, count1 = 0; // Check number of 1's and 0's for ( int i = 0; i < s.Length; i++) { if (s[i] == '0' ) { count0++; } else { count1++; } } string sb = s; // Store difference in number of 1's // and 0's int g = count0 - count1; // l store the value that how much 0's // or 1's we need to add in string int l = n - s.Length; l -= g; // u store the count of // number of 0's we need to insert int u = l / 2; while (u > 0) { sb += '0' ; u--; } if (l % 2 != 0) { sb += '0' ; } while (sb.Length < n) { sb += '1' ; } // Return result return sb; } // Driver code public static void Main() { int N = 7; string S = "001" ; GFG g = new GFG(); // Function call Console.Write(g.find_string(N, S)); } } // This code is contributed by sonjoy_62. |
Javascript
<script> // Javascript program for above approach // Function to build string function find_string(n, s) { // Declaring variable let count0 = 0; let count1 = 0; // Check number of 1's and 0's for (let i = 0; i < s.length; i++) { if (s[i] == '0' ) { count0++; } else { count1++; } } let sb = s; // Store difference in number of 1's // and 0's let g = count0 - count1; // l store the value that how much 0's // or 1's we need to add in string let l = n - s.length; l -= g; // u store the count of // number of 0's we need to insert let u = Math.floor(l / 2); while (u > 0) { sb += '0 '; u--; } if (l % 2 != 0) { sb += ' 0 '; } while (sb.length < n) { sb += ' 1'; } // Return result return sb; } // Driver Code let N = 7; let S = "001" ; // Function call document.write(find_string(N, S)); // This code is contributed by Samim Hossain Mondal. </script> |
0010011
Time Complexity: O(N)
Auxiliary Space: O(1)
Contact Us