921. Minimum Add to Make Parentheses Valid Medium

A parentheses string is valid if and only if:

• It is the empty string,
• 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.

You are given a parentheses string s. In one move, you can insert a parenthesis at any position of the string.

• For example, if s = "()))", you can insert an opening parenthesis to be "(()))" or a closing parenthesis to be "())))".

Return the minimum number of moves required to make s valid.

Example 1:
Input: s = "())"
Output: 1

Example 2:
Input: s = "((("
Output: 3

Approach

Input: A string s containing only '(' and ')'

Output: Return the minimum number of parentheses required to make the string valid

This problem is a typical Valid Parentheses Stack problem, suitable for simulating the parenthesis matching process with a stack.

1. Define a stack stack to store unmatched left parentheses '(';
2. Traverse each character in the string:
   • If it is '(', push it into the stack directly, waiting to be matched.
   • If it is ')':
     • If the stack is not empty, it means there is a left parenthesis that can be matched, so pop one.
     • If the stack is empty, it means there is no left parenthesis to match, so we need to add a left parenthesis, incrementing count by 1.
3. After the traversal:
   • count records the number of left parentheses needed to be added to match extra right parentheses.
   • len(stack) represents the number of unmatched left parentheses, which requires an equal amount of right parentheses to be added.

Implementation

python

class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        stack = []  # Stack to holf unmatched left parentheses
        count = 0   # Track the number of extra right parentheses

        # Iterate through every parenthesis character
        for c in s:
            if c == '(':  
                # Left parenthesis pushed into stack directly, wait for match
                stack.append(c)
            else:  # Encountered right parenthesis ')'
                if stack:
                    # Unmatched left parenthesis exists, match successful, pop one
                    stack.pop()
                else:
                    # No left parenthesis to match, means a left parenthesis is needed
                    count += 1

        # After traversal:
        # - count is the number of left parentheses needed to be added (for extra right parentheses)
        # - len(stack) is the remaining unmatched left parentheses, needing equal right parentheses
        return count + len(stack)

javascript

/**
 * @param {string} s
 * @return {number}
 */
const minAddToMakeValid = function(s) {
    const stack = [];
    let count = 0;

    for (let c of s) {
        if (c == '(') {
            stack.push(c);
        } else {
            if (stack.length) {
                stack.pop();
            } else {
                count ++;
            }
        }
    }

    return count + stack.length;
};

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)

Links

921. Minimum Add to Make Parentheses Valid (English)

921. 使括号有效的最少添加 (Chinese)