Problem of the day:Geeksforgeeks Geeks And The String

 Geeks And The String

MediumAccuracy: 47.57%Submissions: 185+Points: 4

Are You Lost Solving Too Many Random Problems? Try these Problems & Accelerate towards your Goal!

Our geek loves to play with strings, Currently, he is trying to reduce the size of a string by recursively removing all the consecutive duplicate pairs. In other words, He can apply the below operations any number of times.

• Remove all the consecutive duplicate pairs and concatenate the remaining string to replace the original string.

Your task is to find the string with minimum length after applying the above operations.

Note: If the string length become zero after applying operations, return "-1" as a string.

Example 1:

Input:
aaabbaaccd
Output: 
ad
Explanation: 
Remove (aa)abbaaccd =>abbaaccd
Remove a(bb)aaccd => aaaccd
Remove (aa)accd => accd
Remove a(cc)d => ad

Example 2:

Input: 
aaaa
Output: 
Empty String
Explanation: 
Remove (aa)aa => aa
Again removing pair of duplicates then (aa) 
will be removed and we will get 'Empty String'.

Your Task:
This is a function problem. You only need to complete the function removePair() that takes a string as a parameter and returns the modified string. Return an empty string if the whole string is deleted.

Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)

Constraints:
1 <= |str| <= 104

My Solution-

class Solution {

  public:

    string removePair(string s) {

       // code here

        stack<char>st;

        for(int i=0; i<s.length(); i++){

            if(st.empty() || st.top()!=s[i])

            st.push(s[i]);

            else st.pop();

        }

        if(st.size()==0)

        return "-1";

        string ans="";

        while(!st.empty()){

            ans=st.top()+ans;

            st.pop();

        }

        return ans;

    }

};

This solution uses a stack data structure to remove pairs of characters in a given string. The input string is iterated through, and for each character, if the stack is empty or the top of the stack is not equal to the current character, the character is pushed onto the stack. If the top of the stack is equal to the current character, the top of the stack is popped. After the iteration, if the stack is empty, the function returns "-1" indicating that all pairs were removed. Otherwise, the remaining characters in the stack are popped and added to a new string, which is returned as the output. This solution effectively removes all pairs of characters in the input string that are the same.

The time complexity of this solution is O(n) where n is the length of the input string. This is because the solution iterates through the input string once, and for each character, it performs a constant number of operations (i.e., push, pop, or comparison). The space complexity of this solution is O(n) as well. This is because in worst case, the stack will contain all the characters of the input string and it is required to keep all the characters of the input string in the stack. It is important to note that the time and space complexity of this solution is based on the assumption that the stack push, pop, and size operations take constant time. If the stack implementation used has different time complexity for these operations, the time and space complexity of the solution will change accordingly.