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 ')'.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 '('.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) - Iterate over the string once.
Space Complexity: O(1) - Uses a few integer counters.
| 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. |
Minimum Remove to Make Valid Parentheses - Leetcode 1249 - Python • NeetCodeIO • 24,467 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