[LeetCode] Problem 921 - Minimum Add to Make Parentheses Valid

Posted on | In ,

Given a string S of ‘(‘ and ‘)’ parentheses, we add the minimum number of parentheses ( ‘(‘ or ‘)’, and in any positions ) so that the resulting parentheses string is valid.

Formally, a parentheses string is valid if and only if:

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

Given a parentheses string, return the minimum number of parentheses we must add to make the resulting string valid.

Example

No.1

Input: “())”

Output: 1

No.2

Input: “(((“

Output: 3

No.3

Input: “()”

Output: 0

No.4

Input: “()))((“

Output: 4

Note

  1. S.length <= 1000
  2. S only consists of ‘(‘ and ‘)’ characters.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int minAddToMakeValid(String S) {
    int left = 0;
    int right = 0;

    for (char ch : S.toCharArray()) {
        if (ch == '(')
            left++;
        else if (left > 0)
            left--;
        else
            right++;
    }

    return left + right;
}