# Leetcode 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`.`

[Java]

1. Think: use stack to store all the ‘(‘, if we find ’)’, and stack is not empty, pop from the stack.
2. used any non-alphbet character to be a place holder, and remove them at the end
3. use stringbuilder function : setCharAt(position, ‘?’) to modify the string
4. use toString() function to change from StringBuilder to String

--

--

CS new grad, 6 years experience related to supply chain management. Located in Bay area