# Nice Arches Hackerearth problem solution

#### Nice Arches Hackerearth

Nikki’s latest work is writing a story of letters. However, she finds writing story so boring that, after working for three hours, she realized that all she has written are M long words consisting entirely of letters A and B. Having accepted that she will never finish the story in time, poor Nikki has decided to at least have some fun with it by counting bubbly words.

Now Nikki is connecting pairs of identical letters (A with A, B with B) by drawing arches above the word. A given word is bubbly if each letter can be connected to exactly one other letter in such a way that no two arches intersect. So here is your task. Help Nikki count how many words are bubbly.

Input :

The first line of input contains the positive integer M, the number of words written down by Nikki. Each of the following M lines contains a single word consisting of letters A and B, with the length between 2 and 10^5, inclusive. The sum of lengths of all words doesn’t exceed 10^6.

Output :

The first and only line of output must contain the number of bubbly words.

Constraints:

1 <= M <= 100

SAMPLE INPUT
3
ABAB
AABB
ABBA
SAMPLE OUTPUT
2
Explanation
ABAB – It is not bubbly as a(indexed 1) will connect to A(indexed 3) by an arch and when we try to connect B(indexed 2) with B(indexed 4) by an arch then it will intersect with the arch b/w A and A. AABB – It is bubbly as arch b/w A and A will not intersect with the arch b/w B and B. ABBA – It is also bubbly as arches will not intersect. we can draw arches b/w A and A above the arch b/w B and B.

##### Solution
``````#include <iostream>
#include <vector>
using namespace std;
template <class T>
class stack{
public:
stack(){}
bool isEmpty(){
return pool.empty();
}
void clear(){
return pool.clear();
}
void push(T el){
pool.push_back(el);
}
void pop(){
// T el = pool.back();
pool.pop_back();
// return el;
}
T topEl(){
return pool.back();
}
private:
vector<T> pool;
};
int main(){
int m;
int result =0;
cin>>m;
for(int i=0;i<m;i++){
stack <char> S;
string st;
cin>>st;
//cout<<st<<endl;
int len = st.length();
//cout<<len;
S.push(st);
//cout<<S.topEl();//<<endl;
int p=1;
// cout<<st[p]<<endl;
while(p!=len){
if(S.topEl()==st[p]) S.pop();
else
S.push(st[p]);
// cout<<endl<<endl<<S.topEl()<<endl;
p++;
}
if (S.isEmpty()) result ++;
} cout<<result;
return 0;
}``````
``````#include <iostream>
#include <list>
#include <string>
#include <cassert>
using namespace std;
int main()
{
int test,BobblyWords=0;
cin>>test;
list <char> L;
while(test--)
{
string S;
cin>>S;
if(!(S.size()%2))
{
for(int i=0;i<S.size();i++)
{
if(S[i]=='A')
{
if(!L.empty())
{
if(L.back()=='A')
L.pop_back();
else
L.push_back('A');
}
else
L.push_back('A');
}
else
{
if(!L.empty())
{
if(L.back()=='B')
L.pop_back();
else
L.push_back('B');
}
else
L.push_back('B');
}
}
if(!L.size())
++BobblyWords;
L.clear();

}
}
cout<<BobblyWords<<endl;
return 0;
}``````

### hasectic

A web developer(Front end and Back end), and DBA at csdamu.com. Currently working as Salesforce Developer @ Tech Matrix IT Consulting Private Limited. Check me @about.me/s.saifi