921. Minimum Add to Make Parentheses Valid

Description

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

Constraints:

1 <= s.length <= 1000
s[i] is either '(' or ')'.

Solutions

Solution 1: Greedy + Stack

This problem is a classic parenthesis matching problem, which can be solved using "Greedy + Stack".

Iterate through each character $c$ in the string $s$:

If $c$ is a left parenthesis, directly push $c$ into the stack;
If $c$ is a right parenthesis, at this point if the stack is not empty, and the top element of the stack is a left parenthesis, then pop the top element of the stack, indicating a successful match; otherwise, push $c$ into the stack.

After the iteration ends, the number of remaining elements in the stack is the number of parentheses that need to be added.

The time complexity is $O(n)$, and the space complexity is $O(n)$, where $n$ is the length of the string $s$.

Python3JavaC++GoTypeScript

class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        stk = []
        for c in s:
            if c == ')' and stk and stk[-1] == '(':
                stk.pop()
            else:
                stk.append(c)
        return len(stk)

class Solution {
    public int minAddToMakeValid(String s) {
        Deque<Character> stk = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (c == ')' && !stk.isEmpty() && stk.peek() == '(') {
                stk.pop();
            } else {
                stk.push(c);
            }
        }
        return stk.size();
    }
}

class Solution {
public:
    int minAddToMakeValid(string s) {
        string stk;
        for (char c : s) {
            if (c == ')' && stk.size() && stk.back() == '(')
                stk.pop_back();
            else
                stk.push_back(c);
        }
        return stk.size();
    }
};

func minAddToMakeValid(s string) int {
    stk := []rune{}
    for _, c := range s {
        if c == ')' && len(stk) > 0 && stk[len(stk)-1] == '(' {
            stk = stk[:len(stk)-1]
        } else {
            stk = append(stk, c)
        }
    }
    return len(stk)
}

function minAddToMakeValid(s: string): number {
    const stk: string[] = [];
    for (const c of s) {
        if (c === ')' && stk.length > 0 && stk.at(-1)! === '(') {
            stk.pop();
        } else {
            stk.push(c);
        }
    }
    return stk.length;
}

Solution 2: Greedy + Counting

Solution 1 uses a stack to implement parenthesis matching, but we can also directly implement it through counting.

Define a variable cnt to represent the current number of left parentheses to be matched, and a variable ans to record the answer. Initially, both variables are set to $0$.

Iterate through each character $c$ in the string $s$:

If $c$ is a left parenthesis, increase the value of cnt by $1$;
If $c$ is a right parenthesis, at this point if $cnt > 0$, it means that there are left parentheses that can be matched, so decrease the value of cnt by $1$; otherwise, it means that the current right parenthesis cannot be matched, so increase the value of ans by $1$.

After the iteration ends, add the value of cnt to ans, which is the answer.

The time complexity is $O(n)$, and the space complexity is $O(1)$, where $n$ is the length of the string $s$.