Smallest String Obtained By Removing All Occurrences of 01 and 11 from the Binary String

Rhythm Jain
Last Updated: May 13, 2022

Introduction

String questions are increasingly becoming popular among interview questions. Therefore it is necessary to master questions based on string applications to ace technical interviews of big companies.

Let's proceed deeper into the problem and its solution approach.

Problem Statement

The objective is to discover the shortest possible string by deleting all instances of the substrings "01" and "11" from a binary string S as many times as possible and each time concatenate the remaining portions of the text after removing any substrings.

Example:

Input:

S = "0010110"

Output:

“0”

Explanation:

First, we remove “01” from the index 3 string becomes “00110”.

Then we remove “01” from index 1, the string becomes “010”.

Again removing “01” from index 0 we get, “0”.

Because there are no more occurrences of substrings 01 and 11, the string "0" has the shortest possible string of length 1.

Approach: Using Stack

The above problem can be easily solved by using a stack that can help us keep track of the characters of the string encountered so far.

We can observe that our task reduces to removing substring of the pattern “?1” where ? can be either 0 or 1.

Furthermore, the resulting string is always of form 100.. or 00.. where 00.. means zero or more 0’s together.

Algorithm:

  • Initialise a Stack of characters called stk. 
     
  • Traverse the given string and in each iteration:
    • If the stk is empty, push the current binary character S[i] in the stk using the push() function.
    • If the stk is not empty and the current bit S[i] is ‘1’ then remove the top character from the stk using the pop() function.
    • If the current element S[i] is 0 then, push it to the stk using the push() function.
       
  • Append all the elements from top to bottom from the stk and return the output string in reverse order (since stack reverse the relative order of character).

Code

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

void findMinLength(string S)
{
    // Initialize a stack
    stack<int> stk;
    int n = S.length();
    // Traverse the string
    for (int i = 0; i < n; i++)
    {

        // If the stack is empty
        if (stk.empty())

            // Push the character
            stk.push(S[i]);

        // If the character is 1
        else
             if (S[i] == '1')

                // Pop the top element
                stk.pop();

        // Otherwise
        else
            // Push the character
            // to the stack
            stk.push(S[i]);
    }

    // Append the characters
    string output;

    // Until Stack is empty
    while (!stk.empty())
    {
        output.push_back(stk.top());
        stk.pop();
    }
    reverse(output.begin(), output.end());
    cout << output << endl;
}

// Driver Code
int main()
{
    // Given string
    string S = "0010110";

    // Function call
    findMinLength(S);

    return 0;
}

Output

0

Complexity Analysis

Time Complexity: O(N)

Since we are iterating linearly over the string

Space Complexity: O(N) (Stack)

Because in the worst case, we need to store the whole string characters in the stack.

Frequently Asked Questions

  1. What is the time complexity of push() ,pop() and top() operations in stack ?
    In a stack, the complexity of push(), pop(), and top() operations depends upon the implementation of the stack. For the inbuilt STL Stack, the complexity of all the three functions, push(), pop(),.” and top() is O(1).
     
  2. Why the worst-case space complexity is O(N)?
    In the worst case, we mean that neither of the adjacent elements in the string is in a consecutive increasing or decreasing fashion, so in that case, all of the string elements will be pushed into the stack leading to O(N) space.

Key Takeaways

String and application of various data structures on strings are the most critical technical and coding interviews concepts.

On the other hand, Stack seems pretty simple data structure but can help us solve various problems efficiently and quickly.

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think