Menu Close

Jocelyn’s skill is to write stories of letters. But she finds it very boring…[Cprogm]FTC

Jocelyn’s skill is to write stories of letters. But she finds it very boring to write the story, and after three hours of work, Jocelyn realizes that what she wrote is full of A and B letters, and decides that the story will not end on time. So having a little fun with it, at least counting the bubbly words.

Now Jocelyn connects the same pair of letters (A with A, B, and B) by drawing lines on the word. A given word bubble, if it is possible to combine each letter exactly with another letter so that it does not exceed two letters.

Help Jocelyn figure out how many words bubbly.

Input:
The first input contains the positive integer M, the number of words.

Each of the following M lines contains a single word consisting of letters A and B

Output:
Output must contain the number of bubbly words

Example:
          A  B  A  B

First A indexed in 1 and another A letter indexed in 3 rd position. 

First B indexed in 2 and another B letter indexed in 4 th position.

if you draw an arc between A & A, B & B, then the arc will intersect each other.So it is not a bubbly word
#include <stdio.h>
#include <string.h>
struct letters{char x[1000001];};
char stack[1000001];
int top=-1;
void pop(){top--;}
void push(char n)
{
 top++;
 stack[top]=n;
}
int sizeOfStack(){return top+1;}
int main()
{
 struct letters story;
 int n,i,words=0;
 scanf("%d",&n);
 while(n--)
 {
 scanf("%s",story.x);
 for(i=0;i<strlen(story.x);i++)
 {
 if(top==-1 || stack[top]!=story.x[i])
 push(story.x[i]);
 else
 pop();
 }
 if(sizeOfStack()==0)
 words++;
 top=-1;
 }
 printf("%d",words);
return 0;

    }

INPUT_1:
3
ABAB
AABB
ABBA

OUTPUT:
2


INPUT_2:
2
ABAB
AABB

OUTPUT:
1


ILLUSTRATION

EXECUTED USING GCC