0921.md

921. Minimum Add to Make Parentheses Valid

Level:

Topic:

Similar Problem:

• 1249. Minimum Remove to Make Valid Parentheses

Question

You are given a parentheses string s. In one move, you can insert a parenthesis at any position of the string. Return the minimum number of moves required to make s valid.

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

Intuition

With Stack

• store every open parentheses in the stack
• when sees close parenthese and the top of the stack is open paren, pop from stack
• else, add close parenthese to the stack
• lastly, return the size of stack, stack now should remain the invalid parentheses

Use Two Counter Variable for open and close parenthesis

• similar idea with how to add or remove from stack
• because we don't need to know what is in the stack, using counter variables are more straightforward

Code

Stack

Time: O(n)
Space: O(n)

public int minAddToMakeValid(String s) {
    // using stack to keep track of invalid paren
    // whevener sees a valid pair pop from stack

    Stack<Character> stack = new Stack<>();

    for (char c : s.toCharArray()) {
        if (c == '(')
            stack.push(c);
        else if (c == ')') {
            if (!stack.isEmpty() && stack.peek() == '(')
                stack.pop();
            else
                stack.push(c);
        }
    }

    return stack.size();
}

Counter Variables Approach

Time: O(n)
Space: O(1)

public int minAddToMakeValid(String s) {
    // counter for open and close
    int open = 0, close = 0;
    for (char c : s.toCharArray()) {
        if (c == '(')
            open++;
        else if (c == ')') {
            if (open > 0)
                open--;
            else
                close++;
        }
    }
    return open+close;
}