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.
Recommended: What is conio.h and why do we use?
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.