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\).

Python3JavaC++GoTypeScript

class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        ans = cnt = 0
        for c in s:
            if c == '(':
                cnt += 1
            elif cnt:
                cnt -= 1
            else:
                ans += 1
        ans += cnt
        return ans

class Solution {
    public int minAddToMakeValid(String s) {
        int ans = 0, cnt = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') {
                ++cnt;
            } else if (cnt > 0) {
                --cnt;
            } else {
                ++ans;
            }
        }
        ans += cnt;
        return ans;
    }
}

class Solution {
public:
    int minAddToMakeValid(string s) {
        int ans = 0, cnt = 0;
        for (char c : s) {
            if (c == '(')
                ++cnt;
            else if (cnt)
                --cnt;
            else
                ++ans;
        }
        ans += cnt;
        return ans;
    }
};

func minAddToMakeValid(s string) int {
    ans, cnt := 0, 0
    for _, c := range s {
        if c == '(' {
            cnt++
        } else if cnt > 0 {
            cnt--
        } else {
            ans++
        }
    }
    ans += cnt
    return ans
}

function minAddToMakeValid(s: string): number {
    let [ans, cnt] = [0, 0];
    for (const c of s) {
        if (c === '(') {
            ++cnt;
        } else if (cnt) {
            --cnt;
        } else {
            ++ans;
        }
    }
    ans += cnt;
    return ans;
}

Solution 3: Replace + recursion

TypeScriptJavaScript

function minAddToMakeValid(s: string): number {
    const l = s.length;
    s = s.replace('()', '');

    return s.length === l ? l : minAddToMakeValid(s);
}

/**
 * @param {string} s
 * @return {number}
 */
var minAddToMakeValid = function (s) {
    const l = s.length;
    s = s.replace('()', '');
    return s.length === l ? l : minAddToMakeValid(s);
};

Comments