Check if a binary string can be sorted in descending order by removing non-adjacent characters

In this problem, we need to sort the given binary string in descending order by removing only non-adjacent elements.

To solve this problem, we need to remove all 0s that precede 1 in the binary string. If we find two consecutive zeros followed by two consecutive 1s anywhere in the string, it means we cannot sort the string in descending order. Otherwise, we can classify each situation.

Problem Statement - We are given a binary string str of length equal to N. We need to check if a given string can be sorted in descending order by removing multiple non-adjacent characters from the string. the given string. If the string can be sorted in descending order, print "yes"; otherwise, print "no".

Example

Input –  str = "10101100"

Output – “YES”

illustrate

We can sort the string in descending order by removing "0" from the second and fourth position.

Input –  str = "11000"

Output – “YES”

illustrate

Strings have been sorted.

Input –  str = “010001100”

Output – “NO”

illustrate

Here, we need to remove the 0s at the 1st, 3rd, 4th, and 5th positions to sort the string, but we cannot remove adjacent 0s. Alternatively, we could sort the string by removing all "1"s, but this is also impossible because two "1"s are adjacent.

method 1

In this method we will iterate through the string starting from the end. If we find two consecutive "1"s, we break the loop. After that, we check if the string contains two consecutive "0"s. If so, we return false. Otherwise, we return true.

algorithm

• Step 1 - Start using a for loop to iterate through the string from 'len – 2' to 0. Here, 'len' is the length of the given binary string.

• Step 2 - If both str[i] and str[i 1] are equal to "1", terminate the loop using the "break" keyword.

• Step 3 - Now, start traversing the string starting from the i-th index.

• Step 4 - If str[j] and str[j 1] are both equal to '0', return 0. Returns 1 if the loop terminates successfully.

• Step 5 - Print "YES" or "NO" in the driver code based on the return value of the isSortPossible() function.

Example

#include <bits/stdc++.h>
using namespace std;
// removing the non-adjacent characters from the given string to make it sorted in descending order
bool isSortPossible(string str, int len){
   int i, j;
   
   // Traverse the string str from the end
   for (i = len - 2; i >= 0; i--){
   
      // if str[i] and str[i + 1] is equal to 1 then break the loop.
      if (str[i] == '1' && str[i + 1] == '1'){
         break;
      }
   }
   
   // start traversing the string from i
   for (int j = i; j >= 0; j--){
      // If str[j] and str[j + 1] is equal to 0 then return false
      if (str[j] == '0' && str[j + 1] == '0'){
         return 0;
      }
   }
   return 1;
}
int main(){
   string str = "10101100";
   int len = str.length();
   cout << "The sorting of the given binary string is possible by removing non-adjacent characters - " << endl;
   if (isSortPossible(str, len))
      cout << "YES" << endl;
   else
      cout << "NO" << endl;

   return 0;
}

Output

The sorting of the given binary string is possible by removing non-adjacent characters −
YES

Time complexity - O(N), when we iterate over the string.

Space complexity - O(1)

Method 2

In this method we will use the same logic as the first method, but we have optimized the code to make it more readable. Here, instead of using two separate loops, we will use only a single loop to detect two consecutive "1"s after two consecutive "0"s.

algorithm

• Step 1 - Define the "isTwoZeros" variable and initialize it with the "false" value.

• Step 2 - Start iterating the string from index 0 to "len – 1".

• Step 3 - If str[i] and str[I 1] are "0" and "isTwoZeros" equals false, then change the value of "isTwoZeros" to true . This means we got two consecutive zeros in the given string.

• Step 4 - In the else part, if str[i] and str[I 1] are '1' and 'isTwoZeros' equals true, then from the function. This means we get two consecutive "1"s after two consecutive zeros.

• Step 5 - Return true when all iterations of the for loop terminate.

Example

#include <bits/stdc++.h>
using namespace std;
// removing the non-adjacent characters from the given string to make it sorted in descending order
bool isSortPossible(string str, int len){
   // to track if there are two adjacent zeros in the string
   bool isTwoZeros = false;
   
   // traverse the string
   for (int i = 0; i < len - 1; i++){
   
      // if two zeros are adjacent, then change the value of isTwoZeros to true
      if (str[i] == '0' && str[i + 1] == '0' && !isTwoZeros){
         isTwoZeros = true;
      }
      else{
      
         // if we find two adjacent ones after finding two adjacent zeros, then return false
         if (str[i] == '1' && str[i + 1] == '1' && isTwoZeros){
            return false;
         }
      }
   }
   
   // return true if we don't find two adjacent ones after finding two adjacent zeros
   return true;
}
int main(){
   string str = "101001100";
   int len = str.length();
   cout << "The sorting of the given binary string is possible by removing non-adjacent characters - " << endl;
   if (isSortPossible(str, len))
      cout << "YES" << endl;
   else
      cout << "NO" << endl;

   return 0;
}

Output

The sorting of the given binary string is possible by removing non-adjacent characters - 
NO

Time complexity - O(N)

Space complexity - O(1)

in conclusion

We learned two ways to sort a binary string in descending order by removing only non-adjacent characters. Both methods use the same logic with minimal changes to the code. The code for the second approach is more readable than the code for the first approach.

The above is the detailed content of Check if a binary string can be sorted in descending order by removing non-adjacent characters. For more information, please follow other related articles on the PHP Chinese website!