Minimum Add to Make Parentheses Valid
Problem Description
A parentheses string is valid if and only if:
It is the empty string,
It can be written as AB (A concatenated with B), where A and B are valid strings, or
It can be written as (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.
For example, if 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.
Examples:
Input: s = "())"
Output: 1
Explanation: One opening bracket will make the string valid.
Input: s = "((("
Output: 3
Explanation: Three closing brackets will make the string valid.
Constraints:
- 1 <= s.length <= 1000
- s[i] is either '(' or ')'.
Brute Force Approach
Okay, so here's the thought process:
What comes to mind after reading the problem statement?
We need to check how many minimum brackets we need to add to make our string valid. It’s essentially the same as finding how many brackets in the string are unpaired, because we’ll add brackets only to pair them and make the string valid.
Now, how do we check if a pair of brackets is valid or not?
We’ve already done something similar in the "Valid Parenthesis" problem. Did you check that one?
Okay, to check if a string is valid or not, we’ll see if there’s an opening bracket for every closing bracket in the correct order or vice versa.
So, as we go through the string:
- If there’s an opening bracket for a closing bracket, we’ll mark that pair as valid.
- If not, we’ll leave it unmarked.
At the end, we’ll count how many brackets in the string are unmarked. That’s the number of brackets we’ll need to add to make the string valid, and we’ll return that number.
How can we do that?
To determine minimum number of moves to make string valid, we followed a step-by-step process:
Start from the beginning of the string and process each character.
- If an opening bracket ( is found, skip it for now (it may pair with a closing bracket later).
- If a closing bracket ) is found, traverse back through the string to look for an unmarked opening bracket (.
- If an unmarked ( is found, mark both brackets as valid so they won’t be considered again.
- After processing the string, check how many brackets remain unmarked. These are the unpaired brackets.
- The number of unmarked brackets is the minimum number of brackets we need to add to make the string valid.
Let's understand with an example
Let’s dry-run the approach on the string (()))) step by step:
- Initial String: (())))
All brackets are unmarked initially. - Traverse the string:
- First character (: It’s an opening bracket, skip it.
- Second character (: Another opening bracket, skip it.
- Third character ): A closing bracket. Traverse back and find the first unmarked (.
- Mark the pair () as valid.
- Remaining: ( ) ) ).
- Fourth character ): Another closing bracket. Traverse back and find the next unmarked (.
- Mark the pair () as valid.
- Remaining: ) ).
- Fifth character ): A closing bracket. No unmarked ( is left, leave it unmarked.
- Sixth character ): Another closing bracket. No unmarked ( is left, leave it unmarked.
- Count unmarked brackets:
- Unmarked brackets: )) (2 closing brackets).
- Result:
- Minimum brackets to add: 2. (Add 2 opening brackets to pair with the unmarked closing brackets.)
How to code it up:
Here’s how you can code it up step by step:
- Create a boolean vector valid of the same size as the string, initialized to false. This will mark which brackets are paired.
- Use a for loop to iterate through each character of the string.
- If the character is (, skip it (continue to the next iteration).
- Handle a closing bracket ):
- If the character is ), traverse backward from the current position to find an unmarked (.
- If an unmarked ( is found, mark both as valid in the valid vector and break out of the inner loop.
- After the traversal, count all the characters in the string that are not marked valid in the valid vector.
- Return the count of unmarked brackets as the number of brackets to be added.
Code Implementation
1. C++ Try on Compiler
class Solution {
public:
int minAddToMakeValid(string s) {
// Get the length of the input string
int n = s.length();
// Create a vector to track valid brackets, initialized to 0 (false)
vector<bool> valid(n, 0);
// Traverse through the string
for(int i = 0; i < n; i++) {
if(s[i] == '(') {
// If the current character is '(', skip it as it might pair with a ')' later
continue;
} else {
// If the current character is ')', look for an unmarked '('
int j = i - 1;
// Start searching backwards from the current position
while(j >= 0) {
// Check if the current character is '(' and not already marked as valid
if(s[j] == '(' && valid[j] == 0) {
// Mark the '(' as valid
valid[j] = 1;
// Mark the ')' as valid
valid[i] = 1;
// Exit the loop once a valid pair is found
break;
}
// Move one step backward in the search
j--;
}
}
}
// Count the number of unmarked brackets
int count = 0;
for(int i = 0; i < n; i++) {
if(valid[i] == 0) {
// Increment count for each unmarked bracket
count++;
}
}
// Return the number of unmarked brackets as the result
return count;
}
};
2. Java Try on Compiler
class Solution {
public int minAddToMakeValid(String s) {
// Get the length of the input string
int n = s.length();
// Create an array to track valid brackets, initialized to false
boolean[] valid = new boolean[n];
// Traverse through the string
for (int i = 0; i < n; i++) {
if (s.charAt(i) == '(') {
// If the current character is '(', skip it as it might pair with a ')' later
continue;
} else {
// If the current character is ')', look for an unmarked '('
int j = i - 1;
// Start searching backwards from the current position
while (j >= 0) {
// Check if the current character is '(' and not already marked as valid
if (s.charAt(j) == '(' && !valid[j]) {
// Mark the '(' as valid
valid[j] = true;
// Mark the ')' as valid
valid[i] = true;
// Exit the loop once a valid pair is found
break;
}
// Move one step backward in the search
j--;
}
}
}
// Count the number of unmarked brackets
int count = 0;
for (int i = 0; i < n; i++) {
if (!valid[i]) {
// Increment count for each unmarked bracket
count++;
}
}
// Return the number of unmarked brackets as the result
return count;
}
}
3. Python Try on Compiler
class Solution(object):
def minAddToMakeValid(self, s):
# Get the length of the input string
n = len(s)
# Create a list to track valid brackets, initialized to False
valid = [False] * n
# Traverse through the string
for i in range(n):
if s[i] == '(':
# If the current character is '(', skip it as it might pair with a ')' later
continue
else:
# If the current character is ')', look for an unmarked '('
j = i - 1
# Start searching backwards from the current position
while j >= 0:
# Check if the current character is '(' and not already marked as valid
if s[j] == '(' and not valid[j]:
# Mark the '(' as valid
valid[j] = True
# Mark the ')' as valid
valid[i] = True
# Exit the loop once a valid pair is found
break
# Move one step backward in the search
j -= 1
# Count the number of unmarked brackets
count = 0
for i in range(n):
if not valid[i]:
# Increment count for each unmarked bracket
count += 1
# Return the number of unmarked brackets as the result
return count
4. Javascript Try on Compiler
/**
* @param {string} s
* @return {number}
*/
var minAddToMakeValid = function(s) {
// Get the length of the input string
const n = s.length;
// Create an array to track valid brackets, initialized to false
const valid = new Array(n).fill(false);
// Traverse through the string
for (let i = 0; i < n; i++) {
if (s[i] === '(') {
// If the current character is '(', skip it as it might pair with a ')' later
continue;
} else {
// If the current character is ')', look for an unmarked '('
let j = i - 1;
// Start searching backwards from the current position
while (j >= 0) {
// Check if the current character is '(' and not already marked as valid
if (s[j] === '(' && !valid[j]) {
// Mark the '(' as valid
valid[j] = true;
// Mark the ')' as valid
valid[i] = true;
// Exit the loop once a valid pair is found
break;
}
// Move one step backward in the search
j--;
}
}
}
// Count the number of unmarked brackets
let count = 0;
for (let i = 0; i < n; i++) {
if (!valid[i]) {
// Increment count for each unmarked bracket
count++;
}
}
// Return the number of unmarked brackets as the result
return count;
};
Time Complexity: O(n²)
The outer loop processes each character in the input string exactly once. For a string of length n, this loop iterates n times.
For each closing bracket, the algorithm searches backward for the matching opening bracket. In the worst-case scenario, the inner loop might need to traverse through all previous characters, leading to potential i iterations for a closing bracket at position i.
The total operations performed by the inner loop can be expressed as the sum of operations across all outer loop iterations:
Total operations = 0 + 1 + 2 + 3 + ... + (n-1)
This is the sum of the first n-1 integers, which is given by the formula:
Sum = n(n-1)/2
In Big-O notation, considering only the dominant term, we get: O(n²)
The outer loop runs n times, and for each closing bracket, the inner loop could potentially run in O(n) time. Therefore, the overall time complexity due to the nested operations is: O(n²)
The worst-case time complexity of this algorithm is O(n²), primarily due to the inner loop's potential to check all previous characters for matching brackets.
Space Complexity: O(n)
Auxiliary Space: O(n)
Explanation: The only additional data structure used in the solution is the valid array, which tracks whether a bracket has been paired or not.
This array has a size of n (the length of the input string s) because we mark each character in the string to track whether it has been paired.
Thus, the auxiliary space is O(n) because of this extra valid array.
Total Space Complexity: O(n)
Explanation: The input string s itself occupies space proportional to its length, which is O(n). The visited array also occupies O(n) space.
Therefore, the total space used by the algorithm is O(n).
Will Brute Force Work Against the Given Constraints?
For the current solution, the time complexity is O(n²), which is suitable for n ≤ 1000. This means that for each test case the length of string is at most 1000, the solution should execute within the given time limits.
Since O(n²) results in a maximum of 10⁶ operations (for n = 1000), the solution is expected to work well for individual test cases under these constraints, typically allowing around 1–2 seconds for execution.
In most competitive programming environments, problems can handle up to 10⁶ operations per test case, meaning for n ≤ 1000, the solution is efficient enough. However, when multiple test cases are involved, the total number of operations could easily approach 10⁶ operations, the solution ensures that even with n=1000 and multiple test cases, the time complexity remains manageable.
Thus, with O(n²) operations per test case, the solution handles up to 10⁶ operations efficiently, meeting typical competitive programming constraints.
Can we optimize it?
In our earlier implementation, we processed the input string in a reverse manner whenever we encountered a closing bracket. This was done to find its corresponding opening bracket in the correct sequence.
By moving backward, we ensured that the nested or matched brackets were properly identified before proceeding to the next steps of the solution.
This approach, while functional, involved additional overhead in traversing the string multiple times, potentially leading to inefficiencies in cases with deeply nested or numerous brackets.
But what if we don't need to traverse back the entire string to find the suitable opening bracket for a closing bracket?
What if we only store the relevant brackets for every step?
Suppose we encounter a closing bracket ')'. Now, to check if the parentheses are valid, we need to ensure there is a '(' for it in the correct order. So, whenever we encounter a closing bracket, we need to find its corresponding opening bracket.
To achieve this, we can store all opening brackets one by one whenever we encounter them. As we traverse the string, whenever we encounter an opening bracket (, we store it because it might pair with a closing bracket later.
Whenever we encounter a closing bracket ), we check if there is a stored opening bracket available:
- If yes, we remove the matching opening bracket, as the pair is completed.
- If no, we store the closing bracket, as it does not form a valid pair.
After processing the entire string, we will have stored all brackets that did not form valid pairs (both unmatched opening and unmatched closing brackets).
The total count of these unmatched brackets will be our answer.
Basically, we want to compare each closing bracket with the most recent (or last) unmatched opening bracket encountered. To achieve this, we need a way to keep track of the last unmatched opening bracket, ensuring we maintain the correct order. Whenever we encounter an opening bracket, we store it sequentially. When a closing bracket is encountered, we check against the most recent unmatched opening bracket. If they form a valid pair, we pop out the opening bracket; otherwise, we treat the closing bracket as unmatched and store it.
This ensures we efficiently manage and validate the pairs as we process the string.
Wait!! isn't it similar to Last In, First Out (LIFO)??
Which data structure can help us here?
Yes, you're right!
Since we need to keep track of the most recent unmatched opening bracket, we can use a stack. Whenever we encounter an opening bracket, we push it onto the stack. When we encounter a closing bracket, we check the top of the stack to see if there is a matching opening bracket:
- If a match is found, we pop the top of the stack and continue.
- If no match is found or the stack is empty, it means the closing bracket does not have a valid pair, so we'll push the closing bracket in the stack.
At the end of the traversal, the stack will contain all unmatched brackets (both opening and closing). Therefore, the size of the stack gives us the count of unmatched brackets, which is our final answer.
What is a stack?
A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. This means that the last element added to the stack is the first one to be removed. You can think of it like a stack of plates where you add and remove plates from the top.
This approach ensures we efficiently validate the brackets while maintaining the correct order.
Let's understand with an example:
Let’s dry-run the approach on the string "(())))":
- Initialize: Stack is empty.
- First character '(': It's an opening bracket. Push it onto the stack.
Stack: [ ( ] - Second character '(': It's another opening bracket. Push it onto the stack.
Stack: [ ( , ( ] - Third character ')': It's a closing bracket. Check the top of the stack for a matching opening bracket.
- Top of the stack is (, which matches. Pop it.
Stack: [ ( ]
- Top of the stack is (, which matches. Pop it.
- Fourth character ')': It's another closing bracket. Check the top of the stack for a matching opening bracket.
- Top of the stack is (, which matches. Pop it.
Stack: []
- Top of the stack is (, which matches. Pop it.
- Fifth character ')': It's a closing bracket. The stack is empty, so no opening bracket to match.
- This is an unmatched closing bracket. Push it onto the stack.
Stack: [ ) ]
- This is an unmatched closing bracket. Push it onto the stack.
- Sixth character ')': It's another closing bracket. The stack has ) but no opening bracket to match.
- This is also an unmatched closing bracket. Push it onto the stack.
Stack: [ ) , ) ]
- This is also an unmatched closing bracket. Push it onto the stack.
Final Step: The stack contains 2 unmatched closing brackets.
Result: The size of the stack is 2, which is the number of unmatched brackets. Therefore, we need to add 2 opening brackets to make the string valid.
Let's understand with example
How to code it up:
Here's how you can code the approach:
- Initialize a stack.
- Traverse the string.
- If the current character is a closing bracket ')', check if the stack isn't empty and if the top of the stack is an opening bracket '('. If so, pop the top of the stack (this means a valid pair is formed).
- If the above condition isn't met, push the closing bracket ')' onto the stack (this means the closing bracket doesn't have a matching opening bracket).
- If the current character is an opening bracket '(', push it onto the stack (it might form a valid pair later).
- At the end of the traversal, the size of the stack will represent the number of unmatched brackets.
- This size is the final answer.
Code Implementation
1. C++ Try on Compiler
class Solution {
public:
int minAddToMakeValid(string s) {
// Initialize a stack to keep track of unmatched brackets
stack<char> st;
// Traverse through each character in the string
for(auto &c: s) {
// If the current character is a closing bracket
if(c == ')') {
// Check if the stack is not empty and the top element is an opening bracket '('
if(!st.empty() && st.top() == '(') {
// If it's a valid pair '()', pop the opening bracket from the stack
st.pop();
} else {
// Otherwise, push the unmatched closing bracket onto the stack
st.push(')');
}
} else {
// If the current character is an opening bracket '(', push it onto the stack
st.push('(');
}
}
// The size of the stack at the end represents the number of unmatched brackets
return st.size();
}
};2. Java Try on Compiler
import java.util.Stack;
class Solution {
public int minAddToMakeValid(String s) {
// Initialize a stack to keep track of unmatched brackets
Stack<Character> st = new Stack<>();
// Traverse through each character in the string
for (char c : s.toCharArray()) {
// If the current character is a closing bracket
if (c == ')') {
// Check if the stack is not empty and the top element is an opening bracket '('
if (!st.isEmpty() && st.peek() == '(') {
// If it's a valid pair '()', pop the opening bracket from the stack
st.pop();
} else {
// Otherwise, push the unmatched closing bracket onto the stack
st.push(')');
}
} else {
// If the current character is an opening bracket '(', push it onto the stack
st.push('(');
}
}
// The size of the stack at the end represents the number of unmatched brackets
return st.size();
}
}
3. Python Try on Compiler
class Solution:
def minAddToMakeValid(self, s):
# Initialize a stack to keep track of unmatched brackets
st = []
# Traverse through each character in the string
for c in s:
# If the current character is a closing bracket
if c == ')':
# Check if the stack is not empty and the top element is an opening bracket '('
if st and st[-1] == '(':
# If it's a valid pair '()', pop the opening bracket from the stack
st.pop()
else:
# Otherwise, push the unmatched closing bracket onto the stack
st.append(')')
else:
# If the current character is an opening bracket '(', push it onto the stack
st.append('(')
# The size of the stack at the end represents the number of unmatched brackets
return len(st)
4. Javascript Try on Compiler
/**
* @param {string} s
* @return {number}
*/
var minAddToMakeValid = function(s) {
// Initialize a stack to keep track of unmatched brackets
let st = [];
// Traverse through each character in the string
for (let c of s) {
// If the current character is a closing bracket
if (c === ')') {
// Check if the stack is not empty and the top element is an opening bracket '('
if (st.length > 0 && st[st.length - 1] === '(') {
// If it's a valid pair '()', pop the opening bracket from the stack
st.pop();
} else {
// Otherwise, push the unmatched closing bracket onto the stack
st.push(')');
}
} else {
// If the current character is an opening bracket '(', push it onto the stack
st.push('(');
}
}
// The size of the stack at the end represents the number of unmatched brackets
return st.length;
};
Time Complexity: O(n)
The algorithm iterates through each character in the string exactly once. This contributes O(n) to the time complexity.
Each character is processed exactly once during traversal of the string. It can either be pushed onto the stack or popped from the stack, so each character is involved in two operations at most (push and pop).
However, since push and pop operations are constant-time operations O(1), the total number of operations for all characters is still linear with respect to the size of the input string.
Thus, the overall time complexity remains O(n), even though each character is processed twice. The operations are not nested, so the complexity is not squared.
Space Complexity: O(n)
Auxiliary Space: O(n)
Explanation: In this solution, the only extra space used is the stack. At most, the stack will hold all the brackets in the string. In the worst case, the string consists only of all invalid brackets, in which case the stack will hold all n characters.
Therefore, the auxiliary space used by the stack is O(n), where n is the length of the string.
Total Space Complexity: O(n)
Explanation: The total space complexity is O(n) because the space required for the stack and the input string is in the same order of magnitude.
Learning Tip
Now we have successfully tackled this problem, let's try these similar problems.
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.An input string is valid if:Open brackets must be closed by the same type of brackets.Open brackets must be closed in the correct order.Every close bracket has a corresponding open bracket of the same type.
Given a string s of '(' , ')' and lowercase English characters.
Your task is to remove the minimum number of parentheses ( '(' or ')', in any positions ) so that the resulting parentheses string is valid and return any valid string.
Formally, a parentheses string is valid if and only if:
- It is the empty string, contains only lowercase characters, or
- It can be written as AB (A concatenated with B), where A and B are valid strings, or
- It can be written as (A), where A is a valid string.