Leetcode 921: Minimum Add to Make Parentheses Valid
You are given a string consisting of parentheses. In one move, you can insert a parenthesis (either ‘(’ or ‘)’) at any position in the string. Your task is to return the minimum number of moves required to make the string valid, meaning all parentheses are properly balanced.
Problem
Approach
Steps
Complexity
Input: The input consists of a string of parentheses, with each character being either '(' or ')'.
Example: Input: s = "(()))"
Constraints:
• 1 <= s.length <= 1000
• Each character in s is either '(' or ')'.
Output: The output should be an integer representing the minimum number of moves required to make the parentheses string valid.
Example: Output: 1
Constraints:
• The string will contain only '(' and ')'.
Goal: The goal is to calculate how many parentheses need to be added in order to balance the string.
Steps:
• Traverse through the string character by character.
• Use a stack to keep track of unmatched opening parentheses '('.
• For each closing parenthesis ')', pop from the stack if there is a matching opening parenthesis, otherwise count it as a required move.
• At the end, the stack will contain unmatched opening parentheses, and the number of required moves will be equal to the size of the stack.
Goal: Ensure that the input string satisfies the constraints for length and valid parentheses.
Steps:
• The input string will be between 1 and 1000 characters long.
• Each character in the input string will be either '(' or ')'.
Assumptions:
• The input string contains only parentheses.
• Input: Input: s = "())"
• Explanation: The string has one unmatched closing parenthesis. To balance it, we need to insert one opening parenthesis at the beginning. So, the answer is 1.
• Input: Input: s = "((("
• Explanation: The string has three unmatched opening parentheses. To balance it, we need to insert three closing parentheses at the end. So, the answer is 3.
Approach: The approach involves using a stack to keep track of unmatched parentheses while traversing the string. We also count the required moves for unmatched closing parentheses and opening parentheses.
Observations:
• We can use a stack to efficiently manage unmatched parentheses.
• By traversing the string once, we can determine the minimum moves needed.
• A stack is a good choice for tracking unmatched opening parentheses. For unmatched closing parentheses, we can simply count the number of insertions needed.
Steps:
• Step 1: Initialize a stack to store unmatched opening parentheses.
• Step 2: Traverse the string character by character.
• Step 3: If the character is an opening parenthesis '(', push it onto the stack.
• Step 4: If the character is a closing parenthesis ')', check if the stack is empty. If it's not, pop an element from the stack. Otherwise, increment the count for required moves.
• Step 5: After traversing the string, the size of the stack will give the number of unmatched opening parentheses, which also corresponds to the required moves.
Empty Inputs:
• The input string will always have at least one character, so we don't need to handle empty strings.
Large Inputs:
• The algorithm should handle up to 1000 characters efficiently.
Special Values:
• If the string contains only one unmatched opening or closing parenthesis, it will need one move to balance.
Constraints:
• The input string will only contain parentheses, and we will always need to insert parentheses to balance it.
int minAddToMakeValid(string s) {
int res = 0;
stack<int> stk;
for(char &a : s) {
if(a == '(') {
stk.push(a);
} else {
if(stk.empty()) {
res++;
} else {
stk.pop();
}
}
}
res += stk.size();
return res;
}
1 : Function Definition
int minAddToMakeValid(string s) {
Define the function 'minAddToMakeValid', which takes a string 's' and returns an integer representing the number of parentheses needed to balance the string.
2 : Variable Declaration
int res = 0;
Declare an integer variable 'res' to keep track of the number of parentheses to be added for balancing the string.
3 : Stack Declaration
stack<int> stk;
Declare a stack 'stk' to help track the open parentheses.
4 : Loop
for(char &a : s) {
Iterate through each character 'a' in the input string 's'.
5 : Condition
if(a == '(') {
Check if the current character is an opening parenthesis '('.
6 : Stack Operation
stk.push(a);
If the character is an opening parenthesis, push it onto the stack.
7 : Else Condition
} else {
If the current character is not an opening parenthesis, proceed with the else block.
8 : Empty Stack Check
if(stk.empty()) {
Check if the stack is empty, indicating there is no matching opening parenthesis for the closing parenthesis.
9 : Increment Result
res++;
If the stack is empty (no matching opening parenthesis), increment 'res' as one more parenthesis is needed to balance.
10 : Stack Pop
} else {
If the stack is not empty, it means there is a matching opening parenthesis for the closing parenthesis.
11 : Pop Stack
stk.pop();
Pop the matching opening parenthesis from the stack, as the pair is balanced.
12 : Stack Size Addition
res += stk.size();
After processing all characters, add the number of unmatched opening parentheses left in the stack to 'res'.
13 : Return Statement
return res;
Return the final count of parentheses that need to be added to make the string valid.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n) because we only need to traverse the string once.
Best Case: O(1)
Worst Case: O(n)
Description: In the worst case, we may need to store up to n unmatched parentheses in the stack. Hence, the space complexity is O(n).
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus