Try to solve at https://algodaily.com/challenges/minimum-parentheses-removal
---
A string that contains correctly ordered parenthesis `()`, is a valid `parenthesis string`. More specifically, it must meet the following conditions:
- It is an empty string or contains only lowercase characters.
- It can be written as AB (A concatenated with B), where A and B are valid strings.
- It can be written as (A), where A is a valid string.
Given a string `s`, consisting of parenthesis and lowercase English characters. Remove the minimum number of parentheses ( `'('` or `')'` ) to make the resulting parentheses string valid. Multiple valid strings may be possible, but since minimum removal operations are performed, there will be only one correct answer.
For example, consider the following string as input:
````
s = "alg(o(d)a)il)y"
````
All parenthesis are valid except the last one. Removing it will give `alg(o(d)a)ily` which is the correct answer. `alg(o(da)il)y` or `alg(o(d)ail)y` could also be correct answers, but they require more operations, and hence only `alg(o(d)a)ily` is valid.
Constraints
- 1 - `s.length` - 105
- `s[i]` is either'(' , ')', or lowercase English letter.
0 Comments