Last Updated: 20 May, 2021
Ninja and BInary String
Easy
Asked in companies
Ninja is given a binary string ‘S’ of size ‘N’ by his friend, the task is to check if the binary string ‘S’ can be sorted in decreasing order by removing any number of the non-adjacent characters. Since Ninja is busy with some work he is asking for your help. Can you help him?
Note:
A binary string is a string in which all characters are either ‘1’ or ‘0’.
The order is not strictly decreasing.
Input Format:
The first line contains an integer 'T' which denotes the number of test cases or queries to be run.
The first line of each test case contains a single integer ‘N’ denoting the size of the given string.
The second line of each test case contains the string ‘S’.
Output Format:
For each test case, If it is possible to sort the string in decreasing order, then print “true”, otherwise print “false”.
The output of each test case will be printed in a separate line.
Note:
You do not need to input or print anything, as it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 5
1 <= N <= 10 ^ 4
Where ‘T’ is the total number of test cases and ‘N’ is the size of the given string.
Time limit: 1 sec
Approaches
The idea here is to use the fact that while traversing from the end if we encounter 2 consecutive 1s then we can sort the string in decreasing order if and only if after the index which we have found 2 consecutive 1s we have-
- 0-1,1-0 adjacent pair characters- In this case, we can sort the string in decreasing order by removing 0’s from the string as they are not adjacent to each other. For example “1101011” we find 2 consecutive 1s at index 5 and 6 Now in order to sort the string in decreasing order, if we can remove 0s at position 2,4 (Consider 0-based Indexing) as they are not adjacent it results in “11111” which is sorted in decreasing order.
- 1-1 adjacent pair characters- They are already sorted. For example “11111”.
- If we encounter consecutive 0s after consecutive 1s then it is impossible to sort the string in decreasing order. For example “10011” as we cannot remove consecutive 0s at index 1 and 2 in this string, it is impossible to sort the string in decreasing order.
Algorithm:
- Declare a variable ‘check’ for keeping track of whether the string can be sorted or not and a variable ‘Index’ for checking any pair of adjacent characters having the value ‘1’.
- Run a loop from ‘i’ = ’N’ - 1 to ‘i’ = 0.
- Check for any pair of adjacent characters having the value ‘1’.
- If 'str [i] == str[i - 1]' and 'str[i]' = '1'. then set ‘index’ to ‘i’ - 1.
- Now Iterate over the range [‘index’, 0].
- If any pair of adjacent characters having the value ‘0’ are found then update the value of the variable ‘check’ as false and break out of the loop.
- If ‘check’ == true, return true else we return false.