Ninja and BInary String

Easy
0/40
7 upvotes
Asked in companies
Morgan StanleyArcesiumAmazon

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

2
7
1010101
4
0011

Sample Output 1:

true
false

Explanation of Sample Input 1:

Test case 1:

We can remove the non-adjacent characters at indices 1, 3, 5 which modifies the string to “1111”  which is sorted in non-increasing order. So we print “true”.

Test case 2:

We cannot sort the string in non-increasing order by removing adjacent characters so we print “false”.

Sample Input 2:

2
4
1011       
6
000000

Sample Output 2:

true
true

Explanation of Sample Input 2:

Test case 1:

We can remove the non-adjacent character at indices 1,3,5 which modifies the string to “111”  which is a sorted string in non-increasing order. So we print “true”.

Test case 2:

Since the String is already sorted in non-increasing order we print “true”.
Hint

If there exist two adjacent characters having 1s then what makes it impossible to sort the string in decreasing order by removing the non-adjacent characters.

Approaches (1)
Greedy

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.
Time Complexity

O(N), where ‘N’ is the given size of the given string.

 

As we will only be traversing the given string completely. Hence the overall time complexity is O (N).

Space Complexity

O(1)  

 

As we are not using any extra space hence the overall space complexity will be constant.

Code Solution
(100% EXP penalty)
Ninja and BInary String
Full screen
Console