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 ')'.Problem Overview: You get a string containing only '(' and ')'. The goal is to compute the minimum number of parentheses you must add so the final string becomes a valid parentheses sequence. A valid sequence means every opening parenthesis has a matching closing parenthesis and pairs appear in the correct order.
Approach 1: Greedy Balance Tracking (O(n) time, O(1) space)
This approach scans the string once while tracking a running balance of open parentheses. When you see '(', increment the balance because it expects a future closing bracket. When you see ')', decrement the balance. If the balance becomes negative, it means a closing parenthesis appeared without a matching opening one, so you must add an opening parenthesis and reset the balance to zero. After finishing the scan, any remaining positive balance represents unmatched opening parentheses, which require additional closing parentheses.
The key insight: every invalid ')' requires an inserted '(', and every leftover '(' requires a ')'. This greedy rule works because parentheses validity only depends on the running balance, not on rearranging characters. Time complexity is O(n) because you iterate once through the string, and space complexity is O(1) since only counters are stored. This method fits well with problems tagged under Greedy and String.
Approach 2: Stack Simulation (O(n) time, O(n) space)
This method explicitly simulates parentheses matching using a stack. Traverse the string character by character. Push every '(' onto the stack. When encountering ')', check the top of the stack: if an opening parenthesis exists, pop it to form a valid pair. If the stack is empty, the closing parenthesis has no match, so increment the required additions counter.
After processing the entire string, the stack may still contain unmatched opening parentheses. Each remaining element requires one closing parenthesis to make the string valid. The total additions equal the unmatched closing count plus the remaining stack size. This approach has O(n) time complexity because each character is processed once and stack operations are constant time. Space complexity is O(n) due to the stack storing unmatched parentheses. It mirrors the classic pattern used in many Stack problems.
Recommended for interviews: Greedy balance tracking is the expected solution. It achieves the same correctness as the stack simulation but reduces space from O(n) to O(1). Interviewers like to see the stack approach first because it demonstrates understanding of parentheses matching, then the greedy optimization that removes the extra memory.
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.
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 '('.
Time Complexity: O(n) - We traverse the string once.
Space Complexity: O(1) - Only a few integer variables are used.
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.
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.
Time Complexity: O(n) - Iterate over the string once.
Space Complexity: O(1) - Uses a few integer counters.
This problem is a classic parenthesis matching problem, which can be solved using "Greedy + Stack".
Iterate through each character c in the string s:
c is a left parenthesis, directly push c into the stack;c is a right parenthesis, at this point if the stack is not empty, and the top element of the stack is a left parenthesis, then pop the top element of the stack, indicating a successful match; otherwise, push c into the stack.After the iteration ends, the number of remaining elements in the stack is the number of parentheses that need to be added.
The time complexity is O(n), and the space complexity is O(n), where n is the length of the string s.
Python
Java
C++
Go
TypeScript
Solution 1 uses a stack to implement parenthesis matching, but we can also directly implement it through counting.
Define a variable cnt to represent the current number of left parentheses to be matched, and a variable ans to record the answer. Initially, both variables are set to 0.
Iterate through each character c in the string s:
c is a left parenthesis, increase the value of cnt by 1;c is a right parenthesis, at this point if cnt > 0, it means that there are left parentheses that can be matched, so decrease the value of cnt by 1; otherwise, it means that the current right parenthesis cannot be matched, so increase the value of ans by 1.After the iteration ends, add the value of cnt to ans, which is the answer.
The time complexity is O(n), and the space complexity is O(1), where n is the length of the string s.
Python
Java
C++
Go
TypeScript
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| Greedy Balance Tracking | Time Complexity: O(n) - We traverse the string once. |
| Stack Simulation | Time Complexity: O(n) - Iterate over the string once. |
| Greedy + Stack | — |
| Greedy + Counting | — |
| Replace + recursion | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Balance Tracking | O(n) | O(1) | Best general solution when only the count of additions is required and memory efficiency matters |
| Stack Simulation | O(n) | O(n) | Useful for learning parentheses matching or when you need explicit tracking of unmatched characters |
Minimum Add To Make Parentheses Valid | Leetcode 921 Solution • Pepcoding • 9,270 views views
Watch 9 more video solutions →Practice Minimum Add to Make Parentheses Valid with our built-in code editor and test cases.
Practice on FleetCode