Edit Question - KnowledgeHub

Title Body

Question: Remove extra parentheses from the string. e.g. ((a+b))*c => (a+b)*c (a+b)+c => (a+b)+c ((a+b)/(c+d)) => ((a+b)/(c+d)) (a+(((b-c)))*d) => (a+(b-c)*d) and so on. I have come up with the following solution: Approach: I scan through the string and remember (using a map) the index of a opening parenthesis and whether it's extra or not (by default it's extra). If I find a closing parenthesis I check the corresponding opening parenthesis from map and if it's extra then delete both. void removeExtraParentheses(string& S){ map<int, bool> pmap; for(int i = 0; i < S.size(); i++){ map<int, bool>::iterator it; if(S.at(i) == '('){ pmap[i] = true; } else if(S.at(i) == ')'){ it = pmap.end(); it--; if(!(*it).second){ pmap.erase(it); } else{ S.erase(S.begin() + i); S.erase(S.begin() + (*it).first); pmap.erase(it); i = i - 2; } } else{ if(!pmap.empty()){ it = pmap.end(); it--; (*it).second= false; } } } } Time complexity: O(n2) Space: O(n) I'm not too happy with my solution because I'm using extra storage and doing it in quadratic time. Could we do this in O(n) time and O(1) space? If not what is the best one can do?

Tags (comma-separated) Cancel