Minimum Remove to Make Valid Parentheses | February Leetcoding challenge 2021 | Day 19
logo
Manas Sinha
Developer | Designer

By Manas | 19 February 2021

February LeetCoding Challenge 2021

Day 19

Minimum Remove to Make Valid Parentheses

PROBLEM  STATEMENT:
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.
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.
Example 4
Input: s = "(a(b(c)d)"
Output: "a(b(c)d)"
Constraints:
  • 1 <= s.length <= 10^5
  • s[i] is one of  '(' , ')' and lowercase English letters.
Each prefix of a balanced parentheses has a number of open parentheses greater or equal than closed parentheses, similar idea with each suffix.
Check the array from left to right, remove characters that do not meet the property mentioned above, same idea in backward way.

Explanation

This problem is similar to the problem of checking if the parenthesis is balanced or not. We are going to use the same approach however, instead of just telling if it is balanced or unbalanced we are going to remove the parentheses that makes it unbalanced.
ALGORITHM:
  • Maintain a stack.
  • Traverse the string from left to right.
  • Push the index of current character to the stack if it is ‘(‘.
  • If its an alphabet do nothing.
  • If its a ‘)’ we first check if the stack is empty. If it is, that means that the current ‘)’ doesn’t have a corresponding ‘(‘. Replace that character with ‘*’ because it is making the parentheses unbalanced and thus need to be removed from final answer.
  • If the stack is not empty pop the last element from the stack.
  • Finally after traversing the string check if there is any element left in the stack.
  • Replace the character present at the indices left in the stack with ‘*’ because it is again making the parentheses unbalanced and thus need to be removed from final answer 🙂
  • Time complexity : O(n)
  • Space complexity : O(n)

code

C++

class Solution {
public:
    string minRemoveToMakeValid(string s) {
        stack<int> st;
        string res = "";
        for(int i=0;i<s.length();++i){
            if(s[i] == '('){
                st.push(i);
            }
            else if(s[i] == ')'){
                if(st.empty()){
                    s[i] = '*';
                }
                else st.pop();
            }
        }
        while(!st.empty()){
            
            s[st.top()] = '*';
            st.pop();
        }
        for(char c : s){
            if(c!='*') res += c;
            
        }
        return res;
    }
};

PYTHON

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        st = []
        s = list(s)
        for i in range(len(s)):
            c = s[i]
            if c == '(':
                st.append(i)
            elif c == ')':
                if len(st)==0:
                    s[i] = '*'
                else:
                    st.pop()
            
        while len(st):
            s[st[-1]] = '*'
            st.pop()
        res = ''
        for c in s:
            if c != '*':
                res += c
        return res
                

LEAVE A COMMENT

If you like the post leave a comment and share it.

Leave a Reply