Good morning! Here's our prompt for today.

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:

1s = "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.

Note: this problem is similar to Remove Invalid Parentheses, with the difference being that we only want the smallest valid result.

Constraints

• 1 <= s.length <= 105
• s[i] is either'(' , ')', or lowercase English letter.

Try to solve this here or in Interactive Mode.

How do I practice this challenge?

xxxxxxxxxx

var assert = require('assert');

​

function minimumParenthesesRemoval(s) {

    return;

}

​

​

try {

    assert.equal(minimumParenthesesRemoval('a)b(c)d'), 'ab(c)d');

    console.log('PASSED: ' + "`minimumParenthesesRemoval('a)b(c)d')` should return `'ab(c)d'`");

} catch (err) {

    console.log(err);

}

​

try {

    assert.equal(minimumParenthesesRemoval('alg(o(d)a)il)y'), 'alg(o(d)a)ily');

    console.log('PASSED: ' + "`minimumParenthesesRemoval('alg(o(d)a)il)y')` should return `'alg(o(d)a)ily'`");

} catch (err) {

    console.log(err);

}

​

try {

    assert.equal(minimumParenthesesRemoval('))(('), '');

    console.log('PASSED: ' + "`minimumParenthesesRemoval('))((')` should return `''`");

} catch (err) {

    console.log(err);

}

​

try {

Tired of reading? Watch this video explanation!

To change the speed of the video or see it in full screen, click the icons to the right of the progress bar.

Here's how we would solve this problem...

How do I use this guide?