DSA
Minimum Add to Make Parentheses Valid
Strings. Time O(n), Space O(n).
PatternStack (Matching Brackets)OptimalO(n) time · O(n) space
Solve on GeeksforGeeks Key insighttry it first, then reveal
Use a stack to track unmatched opening parentheses.
Practice Link
Using Stack#
Use a stack to track unmatched opening parentheses. When a ')' is seen and the stack is empty, it has no matching '(', so it must be added — increment the unmatched counter. When a ')' is seen and the stack is non-empty, pop the matched '('. After scanning the full string, every '(' remaining in the stack is also unmatched. The answer is the count of unmatched ')' plus the remaining stack size, giving the minimum number of insertions needed to balance the string.
cpp
class Solution {
public:
int minAddToMakeValid(string s) {
stack<char> stk;
int cnt=0;
for(char c: s)
{
if(c=='(')
stk.push(c);
else if(c==')' && stk.empty())
cnt++;
else
stk.pop();
}
return stk.size() + cnt;
}
};
Time Complexity: O(n)
Space Complexity: O(n)