Leetcode: Minimum Add to Make Parentheses Valid

Minimum Add to Make Parentheses Valid

Similar Problems:

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 1:

Input: "())"
Output: 1

Example 2:

Input: "((("
Output: 3

Example 3:

Input: "()"
Output: 0

Example 4:

Input: "()))(("
Output: 4


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

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

  • Solution:
// Blog link: https://code.dennyzhang.com/minimum-add-to-make-parentheses-valid
// Basic Ideas: stack
// Check the item count remainning in the stack
// Complexity: Time O(n), Space O(n)
func minAddToMakeValid(S string) int {
    stack := []rune{}
    for _, ch := range S {
        if ch == ')' && len(stack) != 0 && stack[len(stack)-1] == '(' {
            stack = stack[:len(stack)-1]
        } else {
            stack = append(stack, ch)
    return len(stack)

Share It, If You Like It.

Leave a Reply

Your email address will not be published.