Formatted question description: https://leetcode.ca/all/1249.html

1249. Minimum Remove to Make Valid Parentheses (Medium)

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.

Related Topics:
String, Stack

Solution 1. Scan Left to Right then Right to Left

// OJ: https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    string minRemoveToMakeValid(string s) {
        int left = 0, i, j;
        for (i = 0, j = 0; i < s.size(); ++i) {
            if (isalpha(s[i]) || (s[i] == '(' && ++left) || (s[i] == ')' && --left >= 0)) s[j++] = s[i];
            left = max(left, 0);
        }
        s.resize(j);
        reverse(begin(s), end(s));
        left = 0;
        for (i = 0, j = 0; i < s.size(); ++i) {
            if (isalpha(s[i]) || (s[i] == ')' && ++left) || (s[i] == '(' && --left >= 0)) s[j++] = s[i];
            left = max(left, 0);
        }
        s.resize(j);
        reverse(begin(s), end(s));
        return s;
    }
};

Solution 2. Stack

// OJ: https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/
// Time: O(N)
// Space: O(N)
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()) s[i] = '*';
                else st.pop();
            }
        }
        while (st.size()) {
            s[st.top()] = '*';
            st.pop();
        }
        s.erase(remove(begin(s), end(s), '*'), end(s));
        return s;
    }
};

Java

class Solution {
    public String minRemoveToMakeValid(String s) {
        Stack<Integer> stack = new Stack<Integer>();
        StringBuffer sb = new StringBuffer();
        int length = s.length();
        int deleteCount = 0;
        for (int i = 0; i < length; i++) {
            char c = s.charAt(i);
            if (Character.isLetter(c))
                sb.append(c);
            else if (c == '(') {
                sb.append(c);
                stack.push(i - deleteCount);
            } else if (c == ')') {
                if (!stack.isEmpty()) {
                    sb.append(c);
                    stack.pop();
                } else
                    deleteCount++;
            }
        }
        while (!stack.isEmpty()) {
            int index = stack.pop();
            sb.deleteCharAt(index);
        }
        return sb.toString();
    }
}

// OJ: https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/
// Time: O(N)
// Space: O(1) if changing input string is allowed; otherwise O(N)
class Solution {
public:
    string minRemoveToMakeValid(string s) {
        int j = 0, left = 0;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == '(') ++left;
            else if (s[i] == ')') {
                if (left == 0) continue;
                --left;
            }
            s[j++] = s[i];
        }
        s.resize(j);
        reverse(begin(s), end(s));
        j = 0, left = 0;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == ')') ++left;
            else if (s[i] == '(') {
                if (left == 0) continue;
                --left;
            }
            s[j++] = s[i];
        }
        s.resize(j);
        reverse(begin(s), end(s));
        return s;
    }
};

# 1249. Minimum Remove to Make Valid Parentheses
# https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/

class Solution:
    def minRemoveToMakeValid(self, s: str):
        stack = []
        s = list(s)
        
        for i,c in enumerate(s):
            if c == ")":
                if stack: 
                    stack.pop()
                else:
                    s[i] = ""

            elif c == "(":
                stack.append(i)
            

        while stack:
            s[stack.pop()] = ""

        return "".join(s)
        
    def minRemoveToMakeValid(self, s: str):
        stack = []
        res = [""] * len(s)
        forbidden = set()
        
        for i,c in enumerate(s):
            if c == ")":
                if stack and stack[-1][1] == "(": 
                    stack.pop()
                    res[i] = c
                else:
                    forbidden.add(i)

            elif c == "(":
                res[i] = c
                stack.append((i,c))
            
            else:
                res[i] = c

        if len(stack) > 0:
            forbidden |= set([i for i,_ in stack])

            for i in forbidden:
                res[i] = ""

        return "".join(res)
        
    def minRemoveToMakeValid(self, s: str):
        stack = []
        res = []
        forbidden = set()
        
        for i,c in enumerate(s):
            if c != "(" and c != ")": 
                res.append(c)
            else:
                if c == ")":
                    if stack and stack[-1][1] == "(": 
                        stack.pop()
                        res.append(c)
                    else:
                        forbidden.add(i)
                    
                else:
                    res.append(c)
                    stack.append((i,c))

        if len(stack) > 0:
            forbidden |= set([i for i,_ in stack])
            ans = []
            for i,x in enumerate(s):
                if i not in forbidden:
                    ans.append(x)
            
            return "".join(ans)

        
        return "".join(res)

1249 - Minimum Remove to Make Valid Parentheses

1249. Minimum Remove to Make Valid Parentheses (Medium)

Solution 1. Scan Left to Right then Right to Left

Solution 2. Stack

All Problems

All Solutions