Optimal Adjacent Removal:
Problem
Initially, Chef has a string that contains only lowercase alphabets. In one operation Chef can choose two adjacent same characters (if possible) and remove those two characters from the string and its length will be reduced by two. Now Chef wants to perform this operation in a way such that the final string length should be minimum (possibly empty). Help Chef to find the minimum possible length of the final string if Chef performs the operations optimally.
Input:
- The first and only line of each test case contains a single string .
Output
For each test case, print a single line containing the answer.
Constraints
- contains only lowercase alphabets.
Example 1:
Sample input:
azyyzaSample output:
0
0
Explanation
Example case 1: First remove 'y' and 'y', then 'z' and 'z' and finally 'a' and 'a'. The final string is an empty string.
Example case 2: Chef can't remove any characters.
Example case 3: The only adjacent pair that can be removed is 'p' and 'p'.
Example case 4: One of the possible ways is first to remove 'y' and 'y', then 't' and 't' and finally 'r' and 'r'. The final string is "pq".
Program :
#C
#include<stdio.h>
int MAX = 100000;
char stack[100000];
int top = -1;
int isempty()
{
if(top == -1)
return 1;
else
return 0;
}
int isfull()
{
if(top == MAX)
return 1;
else
return 0;
}
char peek()
{
return stack[top];
}
void pop()
{
if( !isempty() )
{
top = top - 1;
}
}
void push(char data)
{
if( !isfull() )
{
top = top + 1;
stack[top] = data;
}
}
int main()
{
// push items on to the stack
int count=1;
char a[100000];
top = -1;
scanf("%s", a);
push(a[0]);
for (int i = 1; a[i]!= NULL ; i++)
{
if(peek(top-1) == a[i])
pop();
else
push(a[i]);
}
printf("%d\n", top+1);
return 0;
}
#Python
MAX = 100000
stack = ['']*MAX
top = -1
def isempty():
if(top == -1):
return 1
else:
return 0
def isfull():
if(top == MAX):
return 1
else:
return 0
def peek():
return stack[top]
def pop():
global top
if(not isempty()):
top -= 1
def push(data):
global top
if(not isfull()):
top += 1
stack[top] = data
a = input()
push(a[0])
for i in range(1,len(a)):
if(peek() == a[i]):
pop()
else:
push(a[i])
print(top+1)
0 Comments