Minimum Add to Make Parentheses Valid

Leetcode Problem 921: Minimum Add to Make Parentheses Valid

Problem Summary

A parentheses string is valid if it is empty, is the concatenation of two valid strings, or is a valid string wrapped in a matching pair of parentheses. Given a string consisting only of '(' and ')' characters, determine the minimum number of parenthesis insertions (at any position) required to make the string valid.

The string length is between 1 and 1,000.

Techniques

• String
• Stack
• Greedy

Solution

function minAddToMakeValid(s: string): number {
    let corrections = 0
    let open = 0

    for (const char of s) {
        if (char === '(') {
            open++
        } else {
            if (open > 0) {
                open--
            } else {
                corrections++
            }
        }
    }

    return corrections + open
};