Minimum Remove to Make Valid Parentheses - LeetCode Daily Challenge

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.

Try here before watching the video.

Video Solution

Java Code

class Solution {
    public String minRemoveToMakeValid(String s) {
        Stack<Integer> stack = new Stack<>();
        Set<Integer> toBeRemoved = new HashSet<>();
        for(int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if(ch == '(') {
                stack.push(i);
            } else if(ch == ')') {
                if(stack.isEmpty()) {
                    toBeRemoved.add(i);
                } else {
                    stack.pop();
                }
            }
        }

        while(!stack.isEmpty()) {
            toBeRemoved.add(stack.pop());
        }

        StringBuilder sb = new StringBuilder();

        for(int i = 0; i < s.length(); i++) { 
            if(!toBeRemoved.contains(i))
                sb.append(s.charAt(i)); 
        }

        return sb.toString();
    }
}

C++ Code

class Solution {
public:
    string minRemoveToMakeValid(string s) {
        stack<int> stack;
        unordered_set<int> toBeRemoved;
        for(int i = 0; i < s.length(); i++) {
            char ch = s[i];
            if(ch == '(') {
                stack.push(i);
            } else if(ch == ')') {
                if(stack.empty()) {
                    toBeRemoved.insert(i);
                } else {
                    stack.pop();
                }
            }
        }

        while(!stack.empty()) {
            toBeRemoved.insert(stack.top());
            stack.pop();
        }

        string result = "";

        for(int i = 0; i < s.length(); i++) { 
            if(toBeRemoved.find(i) == toBeRemoved.end())
                result += s[i]; 
        }

        return result;
    }
};

Python Code

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        stack = []
        toBeRemoved = set()
        for i, ch in enumerate(s):
            if ch == '(':
                stack.append(i)
            elif ch == ')':
                if not stack:
                    toBeRemoved.add(i)
                else:
                    stack.pop()
        
        while stack:
            toBeRemoved.add(stack.pop())

        result = ''.join(ch for i, ch in enumerate(s) if i not in toBeRemoved)
        return result

Javascript Code

var minRemoveToMakeValid = function(s) {
    const stack = [];
    const toBeRemoved = new Set();
    for (let i = 0; i < s.length; i++) {
        const ch = s[i];
        if (ch === '(') {
            stack.push(i);
        } else if (ch === ')') {
            if (stack.length === 0) {
                toBeRemoved.add(i);
            } else {
                stack.pop();
            }
        }
    }

    while (stack.length > 0) {
        toBeRemoved.add(stack.pop());
    }

    let result = '';
    for (let i = 0; i < s.length; i++) {
        if (!toBeRemoved.has(i)) {
            result += s[i];
        }
    }
    return result;
};

Go Code

func minRemoveToMakeValid(s string) string {
    stack := make([]int, 0)
    toBeRemoved := make(map[int]bool)

    for i, ch := range s {
        if ch == '(' {
            stack = append(stack, i)
        } else if ch == ')' {
            if len(stack) == 0 {
                toBeRemoved[i] = true
            } else {
                stack = stack[:len(stack)-1]
            }
        }
    }

    for _, index := range stack {
        toBeRemoved[index] = true
    }

    result := ""
    for i, ch := range s {
        if _, ok := toBeRemoved[i]; !ok {
            result += string(ch)
        }
    }

    return result
}

Complexity Analysis

Time Complexity: O(N)
Space Complexity: O(N)