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;
    }
};

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();
    }
}

############

class Solution {
    public String minRemoveToMakeValid(String s) {
        Deque<Character> stk = new ArrayDeque<>();
        int x = 0;
        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            if (c == ')' && x == 0) {
                continue;
            }
            if (c == '(') {
                ++x;
            } else if (c == ')') {
                --x;
            }
            stk.push(c);
        }
        StringBuilder ans = new StringBuilder();
        x = 0;
        while (!stk.isEmpty()) {
            char c = stk.pop();
            if (c == '(' && x == 0) {
                continue;
            }
            if (c == ')') {
                ++x;
            } else if (c == '(') {
                --x;
            }
            ans.append(c);
        }
        return ans.reverse().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;
    }
};

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        stk = []
        x = 0
        for c in s:
            if c == ')' and x == 0:
                continue
            if c == '(':
                x += 1
            elif c == ')':
                x -= 1
            stk.append(c)
        x = 0
        ans = []
        for c in stk[::-1]:
            if c == '(' and x == 0:
                continue
            if c == ')':
                x += 1
            elif c == '(':
                x -= 1
            ans.append(c)
        return ''.join(ans[::-1])

############

# 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)

func minRemoveToMakeValid(s string) string {
	stk := []byte{}
	x := 0
	for i := range s {
		c := s[i]
		if c == ')' && x == 0 {
			continue
		}
		if c == '(' {
			x++
		} else if c == ')' {
			x--
		}
		stk = append(stk, c)
	}
	ans := []byte{}
	x = 0
	for i := len(stk) - 1; i >= 0; i-- {
		c := stk[i]
		if c == '(' && x == 0 {
			continue
		}
		if c == ')' {
			x++
		} else if c == '(' {
			x--
		}
		ans = append(ans, c)
	}
	for i, j := 0, len(ans)-1; i < j; i, j = i+1, j-1 {
		ans[i], ans[j] = ans[j], ans[i]
	}
	return string(ans)
}

function minRemoveToMakeValid(s: string): string {
    let left = 0;
    let right = 0;
    for (const c of s) {
        if (c === '(') {
            left++;
        } else if (c === ')') {
            if (right < left) {
                right++;
            }
        }
    }

    let hasLeft = 0;
    let res = '';
    for (const c of s) {
        if (c === '(') {
            if (hasLeft < right) {
                hasLeft++;
                res += c;
            }
        } else if (c === ')') {
            if (hasLeft != 0 && right !== 0) {
                right--;
                hasLeft--;
                res += c;
            }
        } else {
            res += c;
        }
    }
    return res;
}

impl Solution {
    pub fn min_remove_to_make_valid(s: String) -> String {
        let bs = s.as_bytes();
        let mut right = {
            let mut left = 0;
            let mut right = 0;
            for c in bs.iter() {
                match c {
                    &b'(' => left += 1,
                    &b')' if right < left => right += 1,
                    _ => {}
                }
            }
            right
        };
        let mut has_left = 0;
        let mut res = vec![];
        for c in bs.iter() {
            match c {
                &b'(' => {
                    if has_left < right {
                        has_left += 1;
                        res.push(*c);
                    }
                }
                &b')' => {
                    if has_left != 0 && right != 0 {
                        right -= 1;
                        has_left -= 1;
                        res.push(*c);
                    }
                }
                _ => {
                    res.push(*c);
                }
            }
        }
        String::from_utf8_lossy(&res).to_string()
    }
}

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

Welcome to Subscribe On Youtube

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