Minimum Add To Make Parentheses Valid Problem


Description

LeetCode Problem 921.

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:

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

Example 2:

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

Example 3:

1
2
Input: s = "()"
Output: 0

Example 4:

1
2
Input: s = "()))(("
Output: 4

Constraints:

  • 1 <= s.length <= 1000
  • s[i] is either ‘(‘ or ‘)’.


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int minAddToMakeValid(string S) {
        int res = 0, n = S.size(), balance = 0;
        for (int i = 0; i < n; i++) {
            balance += S[i] == '(' ? 1 : -1;
            if (balance == -1) {
                res++;
                balance++;
            }
        }
        return res + balance;
    }
};




Related Posts

Validate Stack Sequences Problem

LeetCode 946. Given two integer arrays pushed and popped each...

Stamping The Sequence Problem

LeetCode 936. You are given two strings stamp and target....

Score Of Parentheses Problem

LeetCode 856. Given a balanced parentheses string s, return the...

Minimum Add To Make Parentheses Valid Problem

LeetCode 921. A parentheses string is valid if and only...

Maximum Width Ramp Problem

LeetCode 962. A ramp in an integer array nums is...

Decoded String At Index Problem

LeetCode 880. You are given an encoded string s. To...