A parentheses string is valid if and only if:
AB (A concatenated with B), where A and B are valid strings, or(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.
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:
Input: s = "())" Output: 1
Example 2:
Input: s = "((("
Output: 3
Constraints:
1 <= s.length <= 1000s[i] is either '(' or ')'.In #921 Minimum Add to Make Parentheses Valid, the goal is to determine the minimum number of parentheses that must be added to make a given string valid. A valid parentheses string requires every opening bracket ( to have a corresponding closing bracket ) in the correct order.
A common and efficient strategy uses a greedy counter approach. Traverse the string and track unmatched opening brackets. When encountering a closing bracket, try to match it with a previous opening bracket. If no match exists, it means an opening bracket must be added. At the end of the traversal, any remaining unmatched opening brackets require corresponding closing brackets.
An alternative way to reason about the problem is using a stack to simulate matching parentheses, pushing openings and popping when a valid closing appears. However, a simple counter-based greedy method achieves the same result with less overhead.
The optimal solution runs in O(n) time by scanning the string once and uses O(1) space when implemented with counters.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy Counter | O(n) | O(1) |
| Stack-Based Matching | O(n) | O(n) |
NeetCodeIO
This approach involves iterating through the string and using a balance counter to track the validity of the sequence.
We increment the balance for every opening parenthesis '(' and decrement it for a closing parenthesis ')'. If, at any point, the balance becomes negative, it means we have an extra closing parenthesis, and we need to increase the count of steps required to balance the string. By the end of the iteration, the balance will also tell us how many opening parentheses need to be closed to make the string valid.
Time Complexity: O(n) - We traverse the string once.
Space Complexity: O(1) - Only a few integer variables are used.
1#include <stdio.h>
2#include <string.h>
3
4int minAddToMakeValid(char * s) {
5 int balance = 0,
The C implementation uses two variables, balance and result. We iterate over the string and adjust the balance for each parenthesis. Whenever balance is negative, it indicates an unmatched ')', and we increase the result to account for the needed '('. Finally, we return the sum of result and balance, where balance accounts for unmatched '('.
In this approach, we leverage a stack structure to simulate parentheses placement, assisting in counting the balance.
Iterate over the string, pushing opening parentheses onto the stack and popping for each encountered closing parenthesis when possible. When a closing parenthesis finds no partner to pop, increase the invalid count, simulating the need for one more opening parenthesis. In the end, the stack length represents unmatched opening parentheses.
Time Complexity: O(n) - Iterate over the string once.
Space Complexity: O(1) - Uses a few integer counters.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
The greedy approach works because each parenthesis can be locally matched or identified as unmatched during a single pass. By immediately resolving matches or counting missing counterparts, you ensure the minimal number of additions required to make the string valid.
Yes, variations of this problem frequently appear in coding interviews. Companies often test candidates on parentheses validation, stack usage, and greedy reasoning. It helps evaluate a candidate's ability to reason about string processing and edge cases.
While a stack can be used to simulate matching parentheses, it is not strictly necessary. A simple counter-based greedy approach is more space-efficient and achieves the same result. However, understanding the stack method helps build intuition for parentheses matching problems.
The optimal approach uses a greedy counter technique. By scanning the string once and tracking unmatched opening parentheses, you can determine how many additions are needed. This approach runs in O(n) time and uses O(1) extra space.
Here, we maintain a stack variable to track open parentheses and an invalid count for unmatched closing parentheses. This eliminates the need for an actual stack structure, only integers are enough.