Min Add to Make Parentheses Valid

JavaView on GFG

Time: O(n)

Space: O(1)

Intuition

Minimum additions to make parenthesis string valid. Track open count and close needed.

Algorithm

1Scan: open++ for (, open-- for ) if open>0 else close++. Answer = open + close.

Common Pitfalls

•Same as LC 921. Track unmatched ( and unmatched ). At end: both counts added give minimum additions.

Min Add to Make Parentheses Valid.java

Java

// Approach: Track open brackets needed and close brackets needed. On '(' increment open; on ')' decrement or increment close.
// Time: O(n) Space: O(1)
import java.util.*;

class Solution {
    public int minParentheses(String s) {
        Stack<Character> st = new Stack<>();
        int count = 0;
        for (char ch : s.toCharArray()) {
            if (ch == '(')
                st.push(ch);
            else {
                if (!st.isEmpty())
                    st.pop();
                else
                    count++;
            }
        }
        return st.isEmpty() ? count : count + st.size();
    }
}

Was this solution helpful?