Stack and Queue in C++ (Part 3)

Data Structure Series in C++

Elimination

Problem Statement

You will be given a binary string S (A binary string is a string which contains only 0 and 1) in which every 1 will eliminate its previously adjacent 0 and itself. After an elimination, if another elimination is possible, it will continue until no further eliminations can be made.

For example, if the sequence is 100110110, then the 3rd and 4th elements, as well as the 6th and 7th elements, will be eliminated, resulting in the string 10110(10 01 1 01 10 — Bold values are eliminated). After that, the 2nd and 3rd elements will be eliminated, resulting in the string 110 (1 01 10 — Bold values are eliminated). After that, no further eliminations can occur.

You need to determine whether the string will be empty after all eliminations.

Note: You need to solve it using STL Stack or Queue only.

Input Format

• First line will contain T, the number of test cases.
• Each test case will contain the string S.

Constraints

1. 1 ≤ T ≤ 10³
2. 1 ≤ |S| ≤ 10⁴

Output Format

• For each test case output YES if the string is empty after all eliminations, NO otherwise.

Sample Input 0

7
01
10
0011
0101
01001110
000111010011
00011

Sample Output 0

YES
NO
YES
YES
NO
YES
NO

Try on your own first.

Wrong Answer:

#include<bits/stdc++.h>
using namespace std;
bool elimination(string &s){
    list<char>final_result;
    for(char c:s){
    if(c=='1'&& !final_result.empty()){
        final_result.pop_back();
    }
    else{
        final_result.push_back(c);
    }
    }
    return final_result.empty();
}
int main (){
    int t;
    cin>>t;
    while(t--){
        string s;
        cin>>s;
        if(elimination(s)){
            cout<<"YES"<<endl;
        }
        else{
            cout<<"NO"<<endl;
        }
    }
    return 0;
}

Correct Answer:

#include<bits/stdc++.h>
using namespace std;
bool elimination(string &s){
    stack<char>final_result;
    for(char c:s){
    if(c=='1'&& !final_result.empty() && final_result.top()=='0'){
        final_result.pop();
    }
    else{
        final_result.push(c);
    }
    }
    return final_result.empty();
}
int main (){
    int t;
    cin>>t;
    while(t--){
        string s;
        cin>>s;
        if(elimination(s)){
            cout<<"YES"<<endl;
        }
        else{
            cout<<"NO"<<endl;
        }
    }
    return 0;
}

Explanation:

Let me break this down step by step.

First, let’s understand what the problem is asking:
1. We have a binary string (containing only 0s and 1s)
2. When a 1 appears, it eliminates itself and the closest preceding 0
3. This process continues until no more eliminations are possible
4. We need to determine if the string becomes empty after all eliminations

Let’s analyze the correct solution:

bool elimination(string &s) {
    stack<char>final_result;
    for(char c:s) {
        if(c=='1' && !final_result.empty() && final_result.top()=='0') {
            final_result.pop();  // Remove the '0'
        }
        else {
            final_result.push(c);
        }
    }
    return final_result.empty();
}

The solution uses a stack, which is perfect for this problem because:
1. We need to keep track of characters in order
2. We need to access and remove the most recently added ‘0’ when we encounter a ‘1’
3. Stack provides O(1) access to the top element

How it works:
1. For each character in the string:
— If we find a ‘1’ AND stack is not empty AND top of stack is ‘0’:
We pop the ‘0’ (eliminating both ‘0’ and current ‘1’)
— Otherwise:
We push the current character onto the stack
2. Finally, we check if stack is empty

Time Complexity: O(n) where n is string length
Space Complexity: O(n) for the stack

Now, let’s see why the wrong solution doesn’t work:

bool elimination(string &s) {
    list<char>final_result;
    for(char c:s) {
        if(c=='1' && !final_result.empty()) {
            final_result.pop_back();
        }
        else {
            final_result.push_back(c);
        }
    }
    return final_result.empty();
}

Problems with this solution:
1. It uses a list instead of a stack (though this isn’t the main issue)
2. The crucial error is in the elimination logic:
— It removes the last element whenever it sees a ‘1’ without checking if it’s a ‘0’
— This means it might incorrectly eliminate a ‘1’ with another ‘1’

Let’s see an example where it fails:
Input: “11”
- Wrong solution would eliminate one ‘1’ with another ‘1’ (incorrect)
- Correct solution would keep both ‘1’s since there’s no ‘0’ to eliminate

Let’s trace both solutions with input “0101”:

Correct Solution:
1. Push ‘0’ → Stack: [0]
2. Push ‘1’ → Found ‘1’ and top is ‘0’, pop → Stack: []
3. Push ‘0’ → Stack: [0]
4. Push ‘1’ → Found ‘1’ and top is ‘0’, pop → Stack: []
Result: Empty (YES)

Wrong Solution:
1. Push ‘0’ → List: [0]
2. Push ‘1’ → Found ‘1’, pop last → List: []
3. Push ‘0’ → List: [0]
4. Push ‘1’ → Found ‘1’, pop last → List: []
Result: Empty (accidentally correct, but wrong logic)

The wrong solution sometimes gives correct answers by coincidence, but it does not follow the actual rules of the problem. Always remember to implement the exact rules given in the problem statement carefully.

Follow my blog, clap it, comment under it, and share. Thank you for your time.