Given a string s of '(' , ')' and lowercase English characters.

Your task is to remove the minimum number of parentheses ( '(' or ')', in any positions ) so that the resulting parentheses string is valid and return any valid string.

Formally, a parentheses string is valid if and only if:


	It is the empty string, contains only lowercase characters, or
	It can be written as AB (A concatenated with B), where A and B are valid strings, or
	It can be written as (A), where A is a valid string.


&nbsp;
Example 1:

Input: s = "lee(t(c)o)de)"
Output: "lee(t(c)o)de"
Explanation: "lee(t(co)de)" , "lee(t(c)ode)" would also be accepted.


Example 2:

Input: s = "a)b(c)d"
Output: "ab(c)d"


Example 3:

Input: s = "))(("
Output: ""
Explanation: An empty string is also valid.


&nbsp;
Constraints:


	1 &lt;= s.length &lt;= 105
	s[i] is either'(' , ')', or lowercase English letter.


class Solution:
    def minRemoveToMakeValid(self, s) :
        stack=[]
        split_str=list(s)
        for i in range(len(s)):
            if s[i]=='(':
                # if current char is '(' then push it to stack
                stack.append(i)
            elif s[i]==')':
                # if current char is ')' then pop top of the stack
                if len(stack) !=0:
                    stack.pop()
                else:
                    # if our stack is empty then we can't pop so make  current char as ''
                    split_str[i]=""
        for i in stack:
            split_str[i]=""
        return '' .join(split_str)
class Solution {
    public String minRemoveToMakeValid(String s) {
        Stack<Integer> stack = new Stack<>();
        for(int i=0;i<s.length();i++) {
            char ch = s.charAt(i);
            if(Character.isAlphabetic(ch))
                continue;
            if(ch == '(')
                stack.push(i);
            else {
                if(!stack.isEmpty() && s.charAt(stack.peek()) == '(')
                    stack.pop();
                else stack.push(i);
            }
        }

        // if(stack.size() == 0) return "";

        StringBuilder result = new StringBuilder();
        HashSet<Integer> set = new HashSet<>(stack);
        for(int i=0;i<s.length();i++)
            if(!set.contains(i))
                result.append(s.charAt(i));

        return result.toString();
    }
}
class Solution {
public:
    string minRemoveToMakeValid(string s) {
        int count = 0;
        for(int i = 0; i < s.size(); i++)
        {

            if(s[i]=='(')
            {
                count++;
            }
            if(s[i]==')')
            {
                if(count==0)
                {
                    s[i]='*';
                }
                else
                {
                    count--;
                }
            }

        }
        if(count==0)
        {
            s.erase(remove(s.begin(), s.end(), '*'), s.end());
            return s;
        }
        for(int i = s.size()-1; i >=0; i--)
        {
            if(s[i]=='(')
            {
                s[i]='*';
                count--;
            }
            if(count==0)
            {
                s.erase(remove(s.begin(), s.end(), '*'), s.end());
                return s;
            }
        }
        return s;
    }
};
var minRemoveToMakeValid = function(s) {
    let validity = 0;
    for(let index = 0; index < s.length; index++) {
        if(s[index] == ')') {
            if(validity == 0) {
                s = s.substring(0,index)+s.substring(index+1);
                index--;
            }
            else {
                validity--;
            }
        }
        else if(s[index] == '(') {
            validity++;
        }
    }
    if(validity > 0) {
        for(let index = s.length-1; index >= 0; index--) {
            if(s[index] == '(') {
                s = s.substring(0,index)+s.substring(index+1);
                validity--;
                if(validity === 0) break;
            }
        }
    }
    return s;
};
Minimum Remove to Make Valid Parentheses