Check If it is Possible to Convert Binary String into Unary String

Last Updated : 11 Dec, 2023

Given a binary string S of length N. You can apply following operation on S any number of times. Choose two adjacent characters, such that both are 1's or 0's. Then invert them, Formally, if both are 0's then into 1's or vice-versa. Then your task is to output YES or NO, by checking that using given operations, Is it possible to convert S into either all 0's or 1's ?

Examples:

Input: N = 6, S = "110110"
Output: YES
Explanation: The operations are performed as:

First operation: S1 = 1 and S2 = 1. Both are same, therefore invert them. Then updated S = 000110
Second operation: S4 = 1 and S5 = 1. Both are same, therefore invert them. Then updated S = 000000
All the string is converted into 0s. Therefore, output is YES. Note that S also can be converted into all 1s by following the sequence: 110110 → 110000 → 110011 → 111111. Both conversions are valid.

Input: N = 7, S = 0101010
Output: NO
Explanation: It can be verified that S can't be converted into all 1s or 0s by using give operation.

Approach: To Solve this problem follow the below idea

It's an observation-based problem. It must be observed that, All occurrence of either number (zero or one) must be existed in pair in order to change the entire S to 1 or 0. Let us take some examples:

001100 = Possible as both 0 and 1 are occurred in pair.
00100 = Possible because 0 occurred in pair.
00101 = Not possible as none of the element occurred in pair.
1100111 = Possible as 0 occurred in pair
Now, we can use Stack to solve this problem:

First, we have to create a Stack.
Iterate on String and follow below steps:
If stack is empty or peek and current characters are different then put current character into Stack
Else If current character and peek character of Stack is same, then pop out the peek element from stack.
If number of elements in stack is either 0 or 1, Then output YES, else NO.

Steps were taken to solve the problem:

Create a Stack of Character data type let say Stk.
Iterate over each character of S using loop and follow below mentioned steps under the scope of loop:
- If (Stk is not empty && Peek character == current character)
  - Pop out the peek character from Stk
- Else
  - Insert character into Stk
If (Size of Stk is less than or equal to 1)
- Output YES
Else
- Output NO

Below is the code to implement the approach:

C++

// code added by flutterfly
#include <iostream>
#include <stack>
using namespace std;

// Function to check the possibility
void Is_possible(long long N, string S)
{
    // Initializing Stack
    stack<char> st;

    // Iterating over String S
    for (char x : S) {
        // If current and peek characters are same
        // Then removing that peek element from Stack
        if (!st.empty() && st.top() == x) {
            st.pop();
        }
        // Else putting the current character into Stack
        else
            st.push(x);
    }

    // If there is at max one character in
    // Stack, Then output YES else NO
    if (st.size() <= 1)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}

// Driver Function
int main()
{
    // Inputs
    long long N = 6;
    string S = "110110";

    // Function call
    Is_possible(N, S);

    return 0;
}

Java

// Java code to implement te approach

import java.util.*;

// Driver Class
public class GFG {
    // Driver Function
    public static void main(String[] args)
    {

        // Inputs
        long N = 6;
        String S = "110110";

        // Function_call
        Is_possible(N, S);
    }

    // Method to check the possibility
    public static void Is_possible(long N, String S)
    {
        // Initializing Stack
        Stack<Character> st = new Stack<>();

        // Iterating over String S
        for (char x : S.toCharArray()) {
            // If current and peek characters are same
            // Then removing that peek element from
            // Stack
            if (!st.empty() && st.peek() == x) {
                st.pop();
            }
            // Else putting current character
            // into Stack
            else
                st.push(x);
        }

        // If there is at max one character in
        // Stack, Then output YES else NO
        if (st.size() <= 1)
            System.out.println("YES");
        else
            System.out.println("NO");
    }
}

Python

# code added by flutterfly
# Python code to implement the approach

# Method to check the possibility
def is_possible(N, S):
    # Initializing Stack
    st = []

    # Iterating over String S
    for x in S:
        # If current and peek characters are the same
        # Then removing that peek element from Stack
        if st and st[-1] == x:
            st.pop()
        # Else putting the current character into Stack
        else:
            st.append(x)

    # If there is at max one character in
    # Stack, Then output YES else NO
    if len(st) <= 1:
        print("YES")
    else:
        print("NO")

# Inputs
N = 6
S = "110110"

# Function call
is_possible(N, S)

// code added by flutterfly
using System;
using System.Collections.Generic;

public class GFG
{
    // Method to check the possibility
    public static void Is_possible(long N, string S)
    {
        // Initializing Stack
        Stack<char> st = new Stack<char>();

        // Iterating over String S
        foreach (char x in S)
        {
            // If current and peek characters are the same
            // Then removing that peek element from Stack
            if (st.Count > 0 && st.Peek() == x)
            {
                st.Pop();
            }
            // Else putting the current character into Stack
            else
            {
                st.Push(x);
            }
        }

        // If there is at max one character in
        // Stack, Then output YES else NO
        if (st.Count <= 1)
            Console.WriteLine("YES");
        else
            Console.WriteLine("NO");
    }

    // Driver Function
    public static void Main()
    {
        // Inputs
        long N = 6;
        string S = "110110";

        // Function call
        Is_possible(N, S);
    }
}

JavaScript

// JavaScript code added by flutterfly

// Method to check the possibility
function isPossible(N, S) {
    // Initializing Stack
    let st = [];

    // Iterating over String S
    for (let x of S) {
        // If current and peek characters are the same
        // Then removing that peek element from Stack
        if (st.length > 0 && st[st.length - 1] === x) {
            st.pop();
        }
        // Else putting the current character into Stack
        else {
            st.push(x);
        }
    }

    // If there is at max one character in
    // Stack, Then output YES else NO
    if (st.length <= 1) {
        console.log("YES");
    } else {
        console.log("NO");
    }
}

// Inputs
let N = 6;
let S = "110110";

// Function call
isPossible(N, S);