Given a binary string s of length N, the task is to find the lexicographically smallest string using infinite number of swaps between 0’s and 1’s.
Examples:
Input: s = “1001001”
Output: 0000111
Explanation: Lexicographically smallest string of 1001001 is only 0000111Input: s = “0001”
Output: 0001
Explanation: Lexicographically smallest string of 0001 is only 0001Input: s = “1”
Output: 1
Explanation: Lexicographically smallest string of 1 is only 1
Naive Approach: The most basic approach to solve this problem is based on below idea:
Since we are allowed to do infinite swaps between 0s and 1s. Therefore while swapping, we will get one such combination where all 0s will come before all 1s.
As by definition, lexicographically smallest binary string must have all 0s before all 1s, therefore, the above such combination will yield the required output.
Now inorder to find such a combination, we can do swapping of 0s and 1s one by one, till we get the required combination where all 0s are before all 1s.
Time Complexity: O(N!), to find all such combinations of given binary string
Auxiliary Space: O(1)
Approach 2: The above approach can be optimised by avoiding the need to find all combinations, based on following observation:
Since we need to find a combination where all 0s come before all 1s, we can sort the given binary string instead, to get the required lexicographically smallest binary string.
Implementation:-
C++
// C++ code to implement the above approach#include <bits/stdc++.h>using namespace std;// Function to find the lexicographically// smallest string using infinite swapsstring lexSmallestBinaryString(string s){ //sorting string sort(s.begin(),s.end()); //returning string return s;}// Driver codeint main(){ string s = "1111000011"; cout << lexSmallestBinaryString(s); return 0;}//code by shubhamrajput6156 |
Java
// Java code to implement the above approachimport java.util.Arrays;public class Main { // Function to find the lexicographically // smallest string using infinite swaps public static String lexSmallestBinaryString(String s) { char[] charArray = s.toCharArray(); // Sorting the string Arrays.sort(charArray); return new String(charArray); } public static void main(String[] args) { String s = "1111000011"; System.out.println(lexSmallestBinaryString(s)); }} |
Python3
# Python code to implement the above approach# Function to find the lexicographically# smallest string using infinite swapsdef lexSmallestBinaryString( s): #sorting string res = ''.join(sorted(s)) #returning string return res;# Driver codes = "1111000011";print(lexSmallestBinaryString(s)); |
C#
// C# code addition for the above approachusing System;public class GFG { // Function to find the lexicographically smallest // string using infinite swaps public static string LexSmallestBinaryString(string s) { char[] charArray = s.ToCharArray(); // Sorting the string Array.Sort(charArray); return new string(charArray); } static public void Main() { // Code string s = "1111000011"; Console.WriteLine(LexSmallestBinaryString(s)); }}// This code is contributed by sankar. |
Javascript
// Function to find the lexicographically// smallest string using infinite swapsfunction lexSmallestBinaryString(s) { // Sorting string let res = s.split('').sort().join(''); // Returning string return res;}// Driver codelet s = "1111000011";console.log(lexSmallestBinaryString(s)); |
0000111111
Time Complexity: O(N*log(N))
Auxiliary Space: O(1)
Efficient approach: The above approach can be further optimised by avoiding the need to sort the given binary string altogether, as per below idea:
Instead of sorting given binary string, we can simply find the count of set and unset bits (0s and 1s) and form a new binary with the same count where all 0s come before all 1s.
Based on the above idea, follow the steps below to implement this approach:
- Count the number of 0s and 1s in given binary string.
- Create a new empty string
- Insert 0s in the empty string equal to the count of 0s in original string.
- Then append 1s in the new string equal to the count of 1s in original string.
- Return the new string as the lexicographically smallest binary string.
Below is the implementation of the above approach:
C++
// C++ code to implement the above approach#include <bits/stdc++.h>using namespace std;// Function to find the count of 0sint countOfXs(string s, char x){ int n = s.length(); int no_of_x = 0; for (int i = 0; i < n; i++) { // if character is 0 // then increase the count of 0's if (s[i] == x) no_of_x++; } return no_of_x;}// Function to find the lexicographically// smallest string using infinite swapsstring lexSmallestBinaryString(string s){ // Variables to count no of 0 and no of 1 int no_of_0 = countOfXs(s, '0'); int no_of_1 = countOfXs(s, '1'); // Create new string to store // the required string s = ""; // Put all 0's first in resultant string for (int i = 0; i < no_of_0; i++) { // Make character equal to 0 s += '0'; } // Append all 1's in resultant string for (int i = 0; i < no_of_1; i++) { // Make character equal to 1 s += '1'; } // Return the resultant string return s;}// Driver codeint main(){ string s = "1111000011"; cout << lexSmallestBinaryString(s); return 0;} |
Java
// Java code to implement the approachimport java.io.*;class GFG{ // Function to find the count of 0s static int countOfXs(String s, char x) { int n = s.length(); int no_of_x = 0; for (int i = 0; i < n; i++) { // if character is 0 // then increase the count of 0's if (s.charAt(i) == x) no_of_x++; } return no_of_x; } // Function to find the lexicographically // smallest string using infinite swaps static String lexSmallestBinaryString(String s) { // Variables to count no of 0 and no of 1 int no_of_0 = countOfXs(s, '0'); int no_of_1 = countOfXs(s, '1'); // Create new string to store // the required string s = ""; // Put all 0's first in resultant string for (int i = 0; i < no_of_0; i++) { // Make character equal to 0 s += '0'; } // Append all 1's in resultant string for (int i = 0; i < no_of_1; i++) { // Make character equal to 1 s += '1'; } // Return the resultant string return s; } public static void main(String[] args) { String s = "1111000011"; System.out.println(lexSmallestBinaryString(s)); }}// This code is contributed by phasing17. |
Python3
# Python3 code for the above approach# Function to find the count of 0sdef countOfXs(s, x): n = len(s) no_of_x = 0 for i in range(n): # if character is 0 # hen increase the count of 0's if s[i] == x: no_of_x += 1 return no_of_x# Function to find the lexicographically# smallest string using infinite swapsdef lexSmallestBinaryString(s): # Variables to count no of 0 and no of 1 no_of_0 = countOfXs(s, '0') no_of_1 = countOfXs(s, "1") # Create new string to store # the required string s = "" # Put all 0's first in resultant string for i in range(no_of_0): # Make character equal to 0 s += "0" # Append all 1's in resultant string for i in range(no_of_1): # Make character equal to 1 s += "1" # Return the resultant string return s# Driver codes = "1111000011" # function callprint(lexSmallestBinaryString(s))# This code is contributed by phasing17 |
C#
// C# code to implement the above approachusing System;class GFG { // Function to find the count of 0s static int countOfXs(string s, char x) { int n = s.Length; int no_of_x = 0; for (int i = 0; i < n; i++) { // if character is 0 // then increase the count of 0's if (s[i] == x) no_of_x++; } return no_of_x; } // Function to find the lexicographically // smallest string using infinite swaps static string lexSmallestBinaryString(string s) { // Variables to count no of 0 and no of 1 int no_of_0 = countOfXs(s, '0'); int no_of_1 = countOfXs(s, '1'); // Create new string to store // the required string s = ""; // Put all 0's first in resultant string for (int i = 0; i < no_of_0; i++) { // Make character equal to 0 s += '0'; } // Append all 1's in resultant string for (int i = 0; i < no_of_1; i++) { // Make character equal to 1 s += '1'; } // Return the resultant string return s; } // Driver code public static void Main() { string s = "1111000011"; Console.Write(lexSmallestBinaryString(s)); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach // Function to find the count of 0s function countOfXs(s, x) { let n = s.length; let no_of_x = 0; for (let i = 0; i < n; i++) { // if character is 0 // then increase the count of 0's if (s[i] == x) no_of_x++; } return no_of_x; } // Function to find the lexicographically // smallest string using infinite swaps function lexSmallestBinaryString(s) { // Variables to count no of 0 and no of 1 let no_of_0 = countOfXs(s, '0'); let no_of_1 = countOfXs(s, '1'); // Create new string to store // the required string s = ""; // Put all 0's first in resultant string for (let i = 0; i < no_of_0; i++) { // Make character equal to 0 s += '0'; } // Append all 1's in resultant string for (let i = 0; i < no_of_1; i++) { // Make character equal to 1 s += '1'; } // Return the resultant string return s; } // Driver code let s = "1111000011"; document.write(lexSmallestBinaryString(s)); // This code is contributed by Potta Lokesh </script> |
0000111111
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
