# Magical String

Posted: 27 Apr, 2021
Difficulty: Easy

## PROBLEM STATEMENT

#### Note :

``````An empty string is also magical.
``````

#### Input Format :

``````The first line contains a single integer ‘T’ representing the number of test cases.

The next ‘T’ lines contain a string ‘S’ given by Haibara.
``````
##### Output Format :
``````For each test case, print the magical string ‘S’ by removing the minimum number of characters.

Output for every test case will be printed in a separate line.
``````
##### Note :
``````You don’t need to print anything; It has already been taken care of.
``````
##### Constraints :
``````1 <= T <= 50
1 <= |S| <= 100

Where ‘T’ is the number of test cases and |S| is the length of the string ‘S.’

Time limit: 1 sec
`````` Approach 1

We will push the first char of the string in a stack and check if the topmost element in the stack and the next element of the string has a difference of 32. Then we will pop the last element from the stack and move to the next element of the string ‘S’. Otherwise, if the difference is not 32 which means that they are not same characters so we will push that element of the string in the stack.

The steps are as follows:

1. Take a stack of char ‘P’ in which we will store our magical string.
2. Iterate through the whole string ‘S’ (say iterator be ‘i’):
1. If ‘P’ is not empty and abs(‘S[i]’ - ’P’.top())  is equal to 32 then pop the last element from the stack ‘P’.
2. Else push S[i] to the Stack ‘P’.
3. Take a string ‘ANS’ to store the result.
4. Now using a while loop push every element of the stack ‘P’ to ‘ANS’ and pop the current element from the stack.
5. Return ‘ANS’