Ninja and BInary String
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

Question

Ninja and BInary String

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

Accepted Answer

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.

Space Complexity: O(1)Explanation:

O(1)

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

Time Complexity: O(n)Explanation:

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).

Java (SE 1.8)


/*
	Time Complexity  :   O(N)
	Space Complexity :   O(1)
	
	Where 'N' is the size of the given string.
*/

public class Solution {

	public static boolean checkSorted(int n, String str) {

		// To check whether the string can be sorted or not.
		boolean check = true;

		int index;

		// Traverse the given string 'str' from end.
		for (index = n - 2; index >= 0; index--) {

			// Check if adjacent character are '11'.
			if (str.charAt(index) == '1' && str.charAt(index + 1) == '1') {
				break;
			}
		}

		// Traverse the string 'str' in the range [index , 0]
		for (int j = index; j >= 0; j--) {

			// If str[j] and str[j + 1] is equal to '0'.
			if (str.charAt(j) == '0' && str.charAt(j+1) == '0') {

				// If found set 'check' to false
				check = false;
				break;
			}
		}

		// If check is false, then it is not possible to sort the string under given
		// conditions
		if (check == false) {
			return false;
		}

		else {
			return true;
		}

	}

}

C++ (g++ 5.4)

/*

    Time Complexity  :   O(N)

    Space Complexity :   O(1)



    Where 'N' is the size of the given string.

*/



bool checkSorted(int N , string &str) {



    // To check whether the string can be sorted or not.

    bool check = true;



    int index;



    // Traverse the given string 'str' from end.

    for (index = N - 2; index >= 0; index--) {



        // Check if adjacent character are '11'.

        if (str[index] == '1'&& str[index + 1] == '1') {

            break;

        }

    }



    // Traverse the string 'str' in the range [index , 0]

    for (int j = index; j >= 0; j--) {



        // If str[j] and str[j + 1] is equal to '0'.

        if (str[j] == '0' && str[j + 1] == '0') {



            // If found set 'check' to false

            check = false;

            break;

        }

    }



    // If check is false, then it is not possible to sort the string under given conditions

    if (check == false) {

        return false;

    }



    else {

        return true;

    }

}

Python (3.5)

'''

    Time Complexity  :   O(N)

    Space Complexity :   O(1)



    Where 'N' is the size of the given string.

'''



def checkSorted(N, str):

	# To check whether the string can be sorted or not.

	check = True	

	index = N -2



    # Traverse the given string str from end.

	while(index >= 0):

		

		# Check if adjacent character are '11'.

		if (str[index] == '1' and str[index + 1] == '1'):

			break

		index -= 1



    # Traverse the string str in the range [index , 0]



	while(index >= 0):

		

		# If str[j] and str[j + 1] is equal to '0'.

		if(str[index] == '0' and str[index + 1] == '0'):

			

			# if found set check to False

			check = False

			break

		index -= 1



    # If check is False, then it is not possible to sort the string under given conditions

	if (check == False):

		return False

	else:

		return True

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:

Input Format:

Output Format:

Note:

Constraints:

Top Amazon Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Amazon Software Developer