Minimum Add to Make Parentheses Valid#

Given a string S consisting of parentheses ( and ), we need to add the minimum number of parentheses ( or ) at any position to make the resulting parentheses string valid.
Formally, a parentheses string is valid if and only if:

• It is the empty string.
• It can be written as AB, where A and B are valid strings.
• It can be written as (A), where A is a valid string. Given a parentheses string, return the minimum number of parentheses we must add to make the resulting string valid.

Example#

Solution#

/**
 * @param {string} S
 * @return {number}
 */
var minAddToMakeValid = function(s) {
    var left=0, right=0;
    Array.prototype.forEach.call(s, v => {
        if(v === "("){
            ++left;
        }else{
            if(left > 0) --left;
            else ++right;
        }
    })
    return left+right;
};

Idea#

Directly traverse once, and during the traversal, count the number of left parentheses, then judge whether to add right parentheses based on encountering right parentheses and count the excess number of left and right parentheses. First, define the number of excess left parentheses left and excess right parentheses right. During the traversal, if encountering left parentheses, regard it as an excess left parentheses +1. If encountering right parentheses, first check if there are excess left parentheses, if yes, use it as the match for the left parentheses and decrement the excess left parentheses by 1, if there are no more left parentheses, it means there are excess right parentheses, then increment the excess right parentheses by 1. Finally, return the number of excess left parentheses and excess right parentheses, which is the number of right and left parentheses that need to be added.

Daily Question#

Reference#