Minimum Remove to Make Valid Parentheses in C++

Suppose we have a string s of '(' , ')' and lowercase English characters. We have to remove the minimum number of parentheses ( '(' or ')', in any positions ) so that the resulting parenthese string is valid and return any valid string. A parentheses string is valid when all of these criteria are fulfilled −

• It is the empty string, contains lowercase characters only, or

• It can be written as the form of AB (A concatenated with B), where A and B are valid strings, or

• It can be written as the form of (A), where A is a valid string.

So if the input is like “a)b(c)d”, then the output will be “ab(c)d”

To solve this, we will follow these steps −

• Define a stack st

• for i in range 0 to size of s

  • if s[i] = ‘(’, then insert i into st

  • otherwise when s[i] is ‘)’, then

    • if stack is not empty, then pop from stack, otherwise s[i] = ‘*’

• while st is not empty,

  • s[top element of stack] = ‘*’

  • pop from stack

• ans := empty string

• for i in range 0 to size of s – 1

  • if s[i] is not ‘*’, then ans := ans + s[i]

• return ans

Let us see the following implementation to get better understanding −

Example

 Live Demo

#include <bits/stdc++.h> using namespace std; class Solution {    public:    string minRemoveToMakeValid(string s) {       stack <int> st;       for(int i = 0; i < s.size(); i++){          if(s[i] == '(')st.push(i);          else if(s[i] == ')'){             if(!st.empty())st.pop();             else s[i] = '*';          }       }       while(!st.empty()){          s[st.top()] = '*';          st.pop();       }       string ans = "";      for(int i = 0; i < s.size(); i++){         if(s[i] != '*')ans += s[i];       }       return ans;   } }; main(){ Solution ob; cout << (ob.minRemoveToMakeValid("a)b(c)d")); }

Input

"a)b(c)d"

Output

ab(c)d