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

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 the 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:

• Initialize 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 the stack reverses 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;
}

You can also try this code with Online C++ Compiler

Run Code

Output

0

You can also try this code with Online C++ Compiler

Run Code

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 of characters in the stack.

Also check out - Substr C++

Frequently Asked Questions

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).

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.

Conclusion

String and application of various data structures on strings are the most critical technical and coding interview concepts. In this article we solved the Smallest String Obtained By Removing All Occurrences of 01 and 11 from the Binary String problem using Stack and discussed the time and space complexity.

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

Recommended problems -

• Beautiful String
• Subsequence of a String
• Find the Shortest Substring in a String

Recommended Reading:

• Print All Subsequences Of A String
• Check if the string is consisting only of a, b, c can be made empty by removing substring ‘abc’ recursively
• Convert Given String S to all 1s by changing all 0s to 1s [i+1, i+K] if S[i] is ‘1’
• Minimizing a string by removing all occurrences of another string
• Minimize a Binary String by Repeatedly Removing Even-Length Substrings of the Same Characters
• Count Strings that do not contain Arc Intersection
• Check if a string is a subsequence of another string using stack
• Object Oriented Programming OOP
   

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, Basics of C++, Basics of Java, Basics of Python, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Cheers!