Last Updated: 27 Apr, 2021
Magical String
Easy
Asked in companies
Haibara hates that Conan is always grasped in murder mysteries. So this time she gives Conan a simple problem to solve in which he is given a string 'S' consisting of lowercase and uppercase characters.
She tells him that a "Magical String" is a string that does not have an adjacent pair of the same characters with one character being lowercase and the other being uppercase. Formally, 'S' is magical if there exits no 'i' such that 'S[i]' is a lowercase character and 'S[ i + 1]' is the same character but in uppercase or vice-versa.
Now, Conan has to make the string 'S' magical by removing the minimum number of characters and return Hibara the magical string hence made.
Your task is to help Conan to obtain the magical string.
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
Approaches
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:
- Take a stack of char ‘P’ in which we will store our magical string.
- Iterate through the whole string ‘S’ (say iterator be ‘i’):
- If ‘P’ is not empty and abs(‘S[i]’ - ’P’.top()) is equal to 32 then pop the last element from the stack ‘P’.
- Else push S[i] to the Stack ‘P’.
- Take a string ‘ANS’ to store the result.
- Now using a while loop push every element of the stack ‘P’ to ‘ANS’ and pop the current element from the stack.
- Return ‘ANS’