Check if binary string can be sorted

Given a binary string consisting of ‘0’ & ‘1’. You can remove any subsequence in given string but can’t pick adjacent indices. Print “POSSIBLE” if string can be sorted else print “NOTPOSSIBLE”.

Examples:

Input: 110
Output: POSSIBLE
Explanation: 
If we remove characters at index 1 & 3 we are left with "1" which is sorted.

Input: 101001111
Output: POSSIBLE
Explanation: 
If we remove characters at index 1 & 3, we are left with "0001111" which is sorted.

Input: 001100
Output: NOTPOSSIBLE
Explanation: 
There is no way we can sort this string by removing a subsequence with no adjacent characters picked.

Approach:
Since we can’t pick adjacent characters so if our string contains string “00” anywhere after string “11”, it is not possible to make the string sorted. Consider “1100”, in this string there is no way we can pick subsequence with no adjacent characters such that string becomes sorted.

Below is the implementation of above approach:

C++

// CPP implementation for above approach
#include <iostream>

using namespace std;

// Driver code
int main() {
  // Given string
  string s = "101001111";

  int o = 0;
  int m = 1;
  for (int i = 0; i < s.size() - 1; i++) {
    // If 2 adjacent elements are same
    if (s[i] == s[i + 1]) {
      // If they are "11" then we set o=1
      if (s[i] == '1')
        o = 1;
      else {
        // If "00" found and o==1
        // we set m=0 and break
        if (o == 1) {
          m = 0;
          break;
        }
      }
    }
  }

  if (m == 1)
    cout << "POSSIBLE";
  else
    cout << "NOTPOSSIBLE";

  return 0;
}

Java

//JAVA implementation for above approach
import java.io.*;

public class CPP {
  //Driver function
  public static void main(String[] args) {
    // Given string
    String s = "101001111";

    // Converting given string to character array
    char[] c = s.toCharArray();
    int o = 0;
    int m = 1;
    for (int i = 0; i < c.length - 1; i++) {
      // If 2 adjacent elements are same
      if (c[i] == c[i + 1]) {
        // If they are "11" then we set o=1
        if (c[i] == '1')
          o = 1;
        else {
          // If "00" found and o==1
          // we set m=0 and break
          if (o == 1) {
            m = 0;
            break;
          }
        }
      }
    }

    if (m == 1)
      System.out.println("POSSIBLE");
    else
      System.out.println("NOTPOSSIBLE");
  }
}

Output:

POSSIBLE

Time complexity: O(n), where n is the length of given string
Space complexity: O(1)

Please write comments if you find anything incorrect. A gentle request to share this topic on your social media profile.

C++

Java

Similar Reads