[leetcode] problem 921 – minimum add to make parentheses valid

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

No.2

No.3

No.4

Note

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public int (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;
}