PROBLEM LINK:
Author: Abhinav Jha
Tester: Ankit Raj Gupta
Editorialist: Abhinav Jha
DIFFICULTY: Simple
PREREQUISITES: Data Structures (Stacks), STL
PROBLEM: Check if a string by deleting the substring IEM from it any number of times.
EXPLANATION:
This is a simple problem based on stacks.
We traverse the input string.
If the character in the string is I or E we push them on stack.
If the character in the string is M, we look at stack:
(a) The top 2 characters on stack are E and I in order respectively: We pop them from stack.
(b) The stack has less than 2 elements or the top 2 characters are not E and I: We push M onto the stack.
After the string traversal is done we still need to look at the stack to check if any more I, E and M characters exist in order.
We repeat the below operations as long as size of stack is greater or equals to 3:
(a) If the top 3 characters of stack are ‘M’, ‘E’ and ‘I’ respectively, we pop them
(b) Else we break the loop (ensure stack is not empty)
Finally we check if the stack is empty or not. The answer is “Yes” when stack is empty and “No” otherwise.
AUTHOR’S SOLUTION:
Author’s solution can be found here