String Editorial

editorial
,
1

Practice

contest

Setter

Tester

Editorialist

DIFFICULTY:
Easy

PREREQUISITES:
Adhoc, stacks

PROBLEM:
Bob favourite Data structure is String. He takes a string and decided to reduce string as much as possible by doing a series of operations. In each operation, he selects a pair of adjacent same letters and deletes them.

Note: If the final string is empty, return Empty String.

EXPLANATION:
To get the fully reduced string, we can use a stack. Suppose we are at an ith position of the string. If the character at top of the stack is the same as S[i], we pop the top element of the stack and move to the i+1th position. Otherwise, if the stack is empty or the top element is not equal to S[i], we will push S[i] to top of the stack and then move to i+1th position. Our final answer is all the elements present in the stack from bottom to top. See the setter’s code for implementation details.

TIME COMPLEXITY:

O(N)

SOLUTIONS:

Setter's Solution 
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
int main(){
    string S;
    cin >> S;
    vector<char>and;
    rep(i,S.length()){
       if(ans.size()==0 or S[i]!=ans.back()) ans.pb(S[i]);
           else ans.pop_back();
       }
   if(ans.size()==0) cout<<"Empty String";
   else{
      for(auto x:ans) cout<<x;
   }
}
2

Below My code is given wrong answer why ??
Please Help Me
```
#include<bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false);cin.tie(0);
#define lli long long int
#define vi vector
#define pb push_back
#include
#define mp map<char,lli>
#define test lli t;cin>>t;while(t–)
using namespace std;
int main()
{
mp arr;
string s,s1="";
cin>>s;
for(lli i=0;i<s.size();i++)
arr[s[i]]+=1;
for(auto it:arr)
if(it.second%2==1)
s1+=it.first;
if(s1.empty())
cout<<“Empty String”<<endl;
else
cout<<s1<<endl;
}

3

The test case where your code fails:

Input

aaabaaa

Expected Output

aba

Your Output

b