MINLEN - Editorial

editorial
, ,
1

PROBLEM LINK:

practice
Contest
Author and Editorialist: sanket

DIFFICULTY:

Easy

PREREQUISITES:

Stack

PROBLEM:

You are given a string. You can perform following operation on given string any number of times.

  • Delete two successive elements of the string if they are same.

After performing the above operation you have to return the least possible length of the string.

EXPLANATION:

We are given a string str. We have to find the minimum length of string after performing given operation on it.

So first declare one stack s. While traversing through string s, if we found stack s empty or if top of stack not equal to ith character of string then push that character, otherwise pop the character.

After traversing through string str, simply print the size of stack.

SOLUTION:

Solutioin 
#include <bits/stdc++.h>
using namespace std;

void solve()
{
    string str;
    cin >> str;

    stack<char> stk;
    string ans = "";

    for (int i = 0; i < str.length(); i++)
    {
        if (stk.empty() || stk.top() != str[i])
        {
            stk.push(str[i]);
        }
        else
        {
            stk.pop();
        }
    }

    cout << stk.size() << endl;
}
int main(){
    int testcase;
    cin>>testcase;

	while(testcase--){
	    solve();
    }
}