Magical String

Easy
0/40
Average time to solve is 20m
profile
Contributed by
2 upvotes
Asked in companies
UberExpedia GroupFareportal

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )

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
Sample Input 1 :
2
sweeEet
codeE
Sample Output 1 :
sweet
cod
Explanation :
In the first test case, either you choose i = 3 or i = 4, both will have the same result “sweet”.

In the second test case, there is only one option i.e i = 3. Hence the result will be “cod”
Sample input 2 :
2
abBAcC
ninja
Sample output 2 :
ninja
Explanation :
In the first test case, first of all, we will choose 'i' =1, which will lead us to “aAcC”. Now we have to choose 'i' = 0, to remove “aA” which will lead us to “cC”. Now we have to remove 'i' = 0 again to make the string magical.

“abBAcC” -> “aAcC” -> “cC” -> “”

In the second test, the given string is already magical. So the result is the same as the input i.e “ninja”.
Hint

The difference between an upper case and a lower case alphabet is 32.

Approaches (1)
Using stack

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’
Time Complexity

O(|S|), where |S| is the size of the string.

 

We iterate over the whole string to check if there are any two characters having difference 32. Hence the overall time complexity is O(|S|).

Space Complexity

O(|S|), where |S| is the size of the string.

 

We are using a stack to store the answer to the string. Hence the space complexity is O(|S|).

Code Solution
(100% EXP penalty)
Magical String
Full screen
Console