Problem:-
You are given a binary string, (string which contains 0's and 1's), You have to perform several operations on this string, in one operation choose a non-empty even length substring containing only 0's or only 1's and remove it from the string.
Your goal is to minimize the final length of the string after performing several operations.It is possible that the final string may become empty, in that case print "KHALI" without quotes.
And it can be proved that there is always an unique string with minimal length after performing the operations.
Input:
- First line of input contains an intger T denoting number of testcases.
- Next T lines of input contains a binary string S.
Output:
- for each testcase print the required minimal string.
Constraints:
- 1 <= T <= 10
- 1 <= |S| <= 105
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation
for the first test case, first remove substring "00", now string will become "1011", now remove "11", hence "10" will be the resulting string.
Code:-
#include<stdio.h>
# define max 100000
char stack[max];
int top=-1;
void push(char ch)
{
top++;
stack[top]=ch;
}
int main()
{
int t;
char str[100000];
scanf("%d",&t);
while(t--)
{
top=-1;
scanf("%s",str);
for(int i=0;str[i];i++)
{
if(top!=-1 && stack[top]==str[i])
{
top--;
}
else
push(str[i]);
}
if(top==-1)
printf("KHALI\n");
else
{
for(int i=0;i<=top;i++)
printf("%c",stack[i]);
printf("\n");
}
}
return 0;
}
0 Comments