Last Updated: 10 Apr, 2021
Greatest Binary String
Easy
Asked in company
In the coding school, the teacher gave his students a binary string ‘bString’, and asked them to make the greatest binary string possible out of it by applying the below-mentioned operations any number of times. The two allowed operations are:
Operation 1: If the string contains the substring "00", the student can replace it with "10". For example, "00010" -> "10010"
Operation 2: If the string contains the substring "10", the student can replace it with "01". For example, "00010" -> "00001"
Assuming that you are the student, find the greatest binary string one can obtain after applying the above operations any number of times.
A Binary string ‘X’ is said to be greater than binary string ‘Y’, if X's decimal representation is greater than Y's decimal representation.
Example:
Let’s say we have bstring as “001” which is an integer 1 in decimal representation. If you apply the above-given operation then you will have bString as “101” which is an integer 5 in decimal representation.
Input format:
The first line of input contains an integer ‘T’, denoting the number of test cases.
The first line of each test case contains a binary string ‘bString’ of 0’s and 1’s.
Output format:
For each test case, print the greatest binary string you can obtain after applying the given operations.
Output for each test case is printed on a separate line.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 10^5
The binary string will only consist of 0’s and 1’s as characters.
Where ‘T’ represents the number of test cases, ‘N’ represents the length of the binary string.
Time Limit: 1 sec
Approaches
- It is a greedy approach where we will first move all the zeros toward the left of the string. This can be done by applying operation 2 on the given binary string.
- Once all the zeros are adjacent to each other, we can apply operation 1 on the string, and finally, we are left with the string that starts with trailing ones.
- And once we can’t apply any more operations from the given ones then we are left with the string that contains atmost one zero, which will be at (location of the first zero in the original string + total number of zeros in the string - 1).
- The binary string that we will get is the greatest.
- So we can conclude that the final string will have only one zero and we have to shift the leftmost 0 equal to the number of zeros that are right the leftmost zero so that we can obtain the maximum binary string.
- And in order to do that, we have to count the total number of zeros to the right of the leftmost zero and that will be our answer.
- For example : 01110010001 -> here the number of 0's after the leftmost zero = 5 . So we need to shift the leftmost 0 five times to the right. 1111101111 this will be the answer.
Algorithm:
- We will create two variables, countZeros initialized to 0 to count the total number of zeros in the string and Start initialized to -1 to find the index of the first zero in the given string.
- We will iterate over the string from the beginning and find the first ‘0’ location in the string and update the value of Start by that index.
- Now check if Start is still equal to -1, then the whole string consists of 1's only. Therefore simply return the given string as it is.
- If the above condition fails, then again iterate over the string and count the total number of zeros in the string and store that value in countZeros. Also, side by side we will make that index equal to ‘1’ as in the end the string will contain all ones except at 1 place.
- Put 0 at (Start + countZeros -1)'th index.
- Then return the string.