Greatest Binary String

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"

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.

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

For the first test case, Given the binary string as “000110”. So we will first apply operation 2 on “000110” and the string will be converted to “000101”.Then again we will apply operation 2 on “000101” and the string will be converted to “000011”. Now will apply operation 1 on “000011” and the string will be converted to “100011”. Then again apply operation 1 on “100011” and it will be converted to “110011”. Now again we will apply operation 1 on “110011” and it will be converted to “111011”. Now we can’t apply any further given operations on the string “111011” so our final output is “111011”. For the second test case, Given the binary string as “01”. Since from the given operations available none of them is applicable so our final output will be “01” itself.

Greedy Solution

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.

Time Complexity

O(N), where ‘N’ is the length of the binary string.

Since we are traversing the string two times, first to find the location of the first zero in the string, and then to count the total number of zeros in the string and also to fill the string with ones side by side. Each of the two traversals takes O(N) time. So overall, time complexity will be O(N).

Space Complexity

O(1),

Since constant space is used. So overall space complexity will be O(1).

Problem statement

Sample Input 1:

Sample Output 1:

Explanation 1:

Sample Input 2:

Sample Output 2: