Minimum Remove to Make Valid Parentheses
Problem Description
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.
Examples:
Input: s = "lee(t(c)o)de)"
Output: "lee(t(c)o)de"
Explanation: "lee(t(co)de)" , "lee(t(c)ode)" would also be accepted.
Input: s = "a)b(c)d"
Output: "ab(c)d"
Input: s = "))(("
Output: ""
Explanation: An empty string is also valid.
Constraints:
- 1 <= s.length <= 10⁵
- s[i] is either '(' , ')', or lowercase English letter.
Brute Force Approach
Okay, so here's the thought process:
What comes to mind after reading the problem statement?
We need to find the minimum number of parentheses we need to remove to make a string valid and return the valid string.
For a string to be valid there must be an opening bracket '(' for each closing bracket ')' in correct order.
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.
- If there is any other character we will skip it.
At the end of the process, we will construct a new string ans by adding every character from the original string s, excluding any parentheses that are invalid.
How can we do that?
To determine minimum remove to make valid parentheses, we followed a step-by-step process:
Start from the beginning of the string and process each character.If any other character is found rather than opening bracket '(' or closing bracket ')', skip it and continue to next 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, add all characters in the ans string except the brackets which are not found valid.
- Return the ans string.
Let's understand with an example:
Input String: "a)b(c)d"
Initialize: ans = "".
- Process 'a':
- Not '(' or ')'. Skip.
- Process ')':
- Closing bracket ')'. Check for unmarked '('. None found. Invalid, skip.
- Process 'b':
- Not '(' or ')'. Skip.
- Process '(':
- Opening bracket '('. Temporarily skip, might pair later.
- Process 'c':
- Not '(' or ')'. Skip.
- Process ')':
- Closing bracket ')'. Find unmarked '(' in stack. Found at index 2.
- Mark both ( and ) as valid.
- Process 'd':
- Not '(' or ')'. Skip.
Since, ')' at index 1 is not found valid, so we will exclude it and take the rest of the string as our answer.
Final Result:
Return "ab(c)d". All valid characters and pairs are preserved, invalid parentheses are removed.
How to code it up:
Here’s how you can code it up step by step:
- Create a vector str to store the characters of the string.
- Create a vector valid of the same size as the string, initialized to 0. This will mark which parentheses are valid (part of a matching pair).
- Use a for loop to iterate through each character of the string.
- For each ')' encountered, traverse backward to find an unmarked '(':
- If an unmarked '(' is found, mark both indices in valid as 1 (indicating they are part of a valid pair).
- Break out of the inner loop once the pair is marked.
- Initialize an empty string ans.
- Traverse the string again:
- If the current character is a parenthesis ('(' or ')') and it is marked valid in valid, add it to ans.
- If the character is not a parenthesis, add it to ans unconditionally.
- Return ans as the final string with all invalid parentheses removed.
Code Implementation
1. C++ Try on Compiler
class Solution {
public:
string minRemoveToMakeValid(string s) {
// Convert the input string to a vector of characters for easy manipulation
vector<char> str(s.begin(), s.end());
int n = s.length();
// Create a vector to mark valid parentheses; initialized to 0 (invalid by default)
vector<int> valid(n, 0);
// First pass: identify valid parentheses
for (int i = 0; i < n; i++) {
// If the current character is a closing parenthesis
if (str[i] == ')') {
// Start traversing backward to find an unmarked opening parenthesis
int j = i - 1;
while (j >= 0) {
// Found an unmarked opening parenthesis
if (str[j] == '(' && valid[j] == 0) {
// Mark both the closing and opening parentheses as valid
valid[i] = 1;
valid[j] = 1;
// Exit the loop as the pair is found
break;
}
// Move backward
j--;
}
}
}
// Second pass: construct the resulting string with valid characters
// Initialize an empty result string
string ans = "";
for (int i = 0; i < n; i++) {
// If the character is a parenthesis
if (str[i] == '(' || str[i] == ')') {
// Add it to the result only if it is marked as valid
if (valid[i])
ans += str[i];
} else {
// Add all non-parenthesis characters unconditionally
ans += str[i];
}
}
// Return the final string with invalid parentheses removed
return ans;
}
};
2. Java Try on Compiler
class Solution {
public String minRemoveToMakeValid(String s) {
// Convert the input string to a character array for easy manipulation
char[] str = s.toCharArray();
int n = s.length();
// Create an array to mark valid parentheses; initialized to 0 (invalid by default)
int[] valid = new int[n];
// First pass: identify valid parentheses
for (int i = 0; i < n; i++) {
// If the current character is a closing parenthesis
if (str[i] == ')') {
// Start traversing backward to find an unmarked opening parenthesis
int j = i - 1;
while (j >= 0) {
// Found an unmarked opening parenthesis
if (str[j] == '(' && valid[j] == 0) {
// Mark both the closing and opening parentheses as valid
valid[i] = 1;
valid[j] = 1;
// Exit the loop as the pair is found
break;
}
// Move backward
j--;
}
}
}
// Second pass: construct the resulting string with valid characters
// Initialize a StringBuilder for the result
StringBuilder ans = new StringBuilder();
for (int i = 0; i < n; i++) {
// If the character is a parenthesis
if (str[i] == '(' || str[i] == ')') {
// Add it to the result only if it is marked as valid
if (valid[i] == 1)
ans.append(str[i]);
} else {
// Add all non-parenthesis characters unconditionally
ans.append(str[i]);
}
}
// Return the final string with invalid parentheses removed
return ans.toString();
}
}
3. Python Try on Compiler
class Solution:
def minRemoveToMakeValid(self, s):
# Convert the input string to a list of characters for easy manipulation
str_arr = list(s)
n = len(s)
# Create a list to mark valid parentheses; initialized to 0 (invalid by default)
valid = [0] * n
# First pass: identify valid parentheses
for i in range(n):
# If the current character is a closing parenthesis
if str_arr[i] == ')':
# Start traversing backward to find an unmarked opening parenthesis
j = i - 1
while j >= 0:
# Found an unmarked opening parenthesis
if str_arr[j] == '(' and valid[j] == 0:
# Mark both the closing and opening parentheses as valid
valid[i] = 1
valid[j] = 1
# Exit the loop as the pair is found
break
# Move backward
j -= 1
# Second pass: construct the resulting string with valid characters
# Initialize a result string
ans = []
for i in range(n):
# If the character is a parenthesis
if str_arr[i] in '()':
# Add it to the result only if it is marked as valid
if valid[i]:
ans.append(str_arr[i])
else:
# Add all non-parenthesis characters unconditionally
ans.append(str_arr[i])
# Return the final string with invalid parentheses removed
return ''.join(ans)
4. Javascript Try on Compiler
/**
* @param {string} s
* @return {string}
*/
var minRemoveToMakeValid = function(s) {
// Convert the input string to an array of characters for easy manipulation
const str = s.split('');
const n = s.length;
// Create an array to mark valid parentheses; initialized to 0 (invalid by default)
const valid = new Array(n).fill(0);
// First pass: identify valid parentheses
for (let i = 0; i < n; i++) {
// If the current character is a closing parenthesis
if (str[i] === ')') {
// Start traversing backward to find an unmarked opening parenthesis
let j = i - 1;
while (j >= 0) {
// Found an unmarked opening parenthesis
if (str[j] === '(' && valid[j] === 0) {
// Mark both the closing and opening parentheses as valid
valid[i] = 1;
valid[j] = 1;
// Exit the loop as the pair is found
break;
}
// Move backward
j--;
}
}
}
// Second pass: construct the resulting string with valid characters
// Initialize a result array
let ans = [];
for (let i = 0; i < n; i++) {
// If the character is a parenthesis
if (str[i] === '(' || str[i] === ')') {
// Add it to the result only if it is marked as valid
if (valid[i])
ans.push(str[i]);
} else {
// Add all non-parenthesis characters unconditionally
ans.push(str[i]);
}
}
// Return the final string with invalid parentheses removed
return ans.join('');
};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
We again traversed the string to take only valid characters in our answer, which took the time complexity of O(n).
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 additional data structure used in the solution is the valid array, which tracks whether a bracket has been paired or not and character array representing string s.
Both the array has a size of n (the length of the input string s) and 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 and character array.
Total Space: 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 not suitable for n ≤ 10⁵. This means that for each test case, where the length of the string is at most 10⁵, the solution might not execute within the given time limits.
However, due to less strict test cases and the effective use of the break statement inside the loop, the solution is accepted on Leetcode.
Since O(n²) results in a maximum of 10¹⁰ operations (for n = 10⁵), the solution is not expected to work well for larger test cases. In most competitive programming environments, problems can handle up to 10⁶ operations per test case, meaning that for n ≤ 10⁵, the solution with 10¹⁰ operations is not efficient enough.
When multiple test cases are involved, the total number of operations could easily exceed this limit and approach 10¹⁰ operations, especially when there are many test cases or the value of n increases.
Thus, while the solution meets the time limits for a single test case, the O(n²) time complexity poses a risk for Time Limit Exceeded (TLE) errors when handling larger input sizes or multiple test cases. This can be a challenge for competitive programming problems with larger inputs or numerous test cases.
Can we optimize it?
In our earlier implementation, we processed the input string in reverse whenever we encountered a closing bracket to find its corresponding opening bracket. This ensured the brackets were matched correctly, but it involved traversing the string multiple times.
This approach could become inefficient, especially in cases with deeply nested or numerous brackets.
But what if we didn’t need to traverse back through the string to find a suitable opening bracket for each closing bracket?
What if we only tracked the relevant brackets as we processed the string?
Here’s how:
When we encounter a closing bracket ')', we need to check if there’s an opening bracket '(' available to form a valid pair. To do this, we can store the indices of all unmatched opening brackets as we traverse the string.
- When we encounter an opening bracket '(':
We store its index because it might pair with a closing bracket later. - When we encounter a closing bracket ')':
- If there’s an unmatched opening bracket stored, we use it to form a valid pair and remove it from our tracking (pop the most recent unmatched opening bracket).
- If there’s no unmatched opening bracket, we store the closing bracket’s index, as it does not form a valid pair.
At the end of this process, we’ll have all unmatched brackets (both opening and closing) stored. These are invalid, and we can exclude them from the final result.
Finally, to construct the result string, we add all characters from the input string except for the ones marked as invalid.
In essence, this approach ensures that every closing bracket is compared with the most recent (last) unmatched opening bracket. By storing unmatched brackets and processing them sequentially, we efficiently validate pairs and avoid the overhead of traversing backward through the string repeatedly.
Wait!! isn't it similar to Last In, First Out (LIFO)??
Which data structure can help us here?
Yes, you're right!
To keep track of the most recent unmatched opening bracket, we can use a stack.
Here's how it works:
Whenever we encounter an opening bracket '(', we simply push its index onto the stack. This is because it might pair with a closing bracket later.
When we encounter a closing bracket ')', we check the top of the stack:
- If there's an unmatched opening bracket ('(') on top, it forms a valid pair, so we pop the stack and move on.
- If the stack is empty or there's no matching opening bracket, it means the closing bracket is unmatched. In that case, we push its index onto the stack.
After processing the entire string, the stack will contain the indices of all unmatched brackets—both opening and closing. These are the invalid brackets, which we can exclude from the final result string.
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 allows us to efficiently manage and validate the brackets without needing extra traversals.
Let's understand with an example:
Let's take an Input string: a)b(c)d
- Index 0 ('a'):
- Not a bracket → Stack: []
- Index 1 (')'):
- Stack is empty → Push index 1 → Stack: [1]
- Index 2 ('b'):
- Not a bracket → Stack: [1]
- Index 3 ('('):
- Push index 3 → Stack: [1, 3]
- Index 4 ('c'):
- Not a bracket → Stack: [1, 3]
- Index 5 (')'):
- Match found with '(' at index 3 → Pop index 3 → Stack: [1]
- Index 6 ('d'):
- Not a bracket → Stack: [1]
Final Stack: [1] (unmatched closing bracket at index 1) [invalid index].
Output: Skip index 1 → Result: ab(c)d.
How to code it up:
- Initialize a stack to track unmatched parentheses.
- Traverse the string character by character:
- If the current character is a closing bracket ')':
- Check if the stack isn’t empty and the top of the stack is an opening bracket '('.
- If so, pop the top of the stack (indicating a valid pair is formed).
- If the condition isn't met, push the closing bracket onto the stack (it has no matching opening bracket).
- If the current character is an opening bracket '(', push it onto the stack (it might form a valid pair later).
- Initialize a boolean array valid with all indices marked as true (indicating all characters are initially valid).
- Mark invalid indices:
- For each index in the stack (unmatched parentheses), mark the corresponding index in the valid array as false.
- Initialize an empty string ans to store the final result.
- Traverse the string again:
- If the current character is marked true in the valid array, add it to ans.
- Return the final string ans with all invalid parentheses removed.
Code Implementation
1. C++ Try on Compiler
class Solution {
public:
string minRemoveToMakeValid(string s) {
// Get the length of the input string
int n = s.length();
// Stack to track the indices of unmatched opening brackets
stack<int> st;
// First pass: Traverse the string to identify unmatched brackets
for(int i = 0; i < n; i++) {
// If the current character is an opening bracket '(', push its index onto the stack
if(s[i] == '(')
st.push(i);
// If the current character is a closing bracket ')'
else if(s[i] == ')') {
// If there's an unmatched opening bracket '(', pop the top of the stack (valid pair found)
if(!st.empty() && s[st.top()] == '(')
st.pop();
// If no matching opening bracket, push the current closing bracket's index to the stack
else
st.push(i);
}
}
// If the stack is empty, the string is already valid, so return the original string
if(st.size() == 0)
return s;
// Create a boolean vector `valid` to mark which characters should be kept (true means valid)
vector<bool> valid(n, 1);
// Mark all indices in the stack as invalid
while(!st.empty()) {
// Mark the current index as invalid
valid[st.top()] = 0;
// Remove the index from the stack
st.pop();
}
// Construct the result string by adding only the valid characters
string res = "";
for(int i = 0; i < n; i++) {
// If the current character is valid, add it to the result string
if(valid[i])
res += s[i];
}
// Return the final string with invalid parentheses removed
return res;
}
};
2. Java Try on Compiler
import java.util.Stack;
class Solution {
public String minRemoveToMakeValid(String s) {
// Get the length of the input string
int n = s.length();
// Stack to track the indices of unmatched opening brackets
Stack<Integer> st = new Stack<>();
// First pass: Traverse the string to identify unmatched brackets
for (int i = 0; i < n; i++) {
// If the current character is an opening bracket '(', push its index onto the stack
if (s.charAt(i) == '(')
st.push(i);
// If the current character is a closing bracket ')'
else if (s.charAt(i) == ')') {
// If there's an unmatched opening bracket '(', pop the top of the stack (valid pair found)
if (!st.isEmpty() && s.charAt(st.peek()) == '(')
st.pop();
// If no matching opening bracket, push the current closing bracket's index to the stack
else
st.push(i);
}
}
// If the stack is empty, the string is already valid, so return the original string
if (st.isEmpty())
return s;
// Create a boolean array valid to mark which characters should be kept (true means valid)
boolean[] valid = new boolean[n];
for (int i = 0; i < n; i++) valid[i] = true;
// Mark all indices in the stack as invalid
while (!st.isEmpty()) {
// Mark the current index as invalid
valid[st.pop()] = false;
}
// Construct the result string by adding only the valid characters
StringBuilder res = new StringBuilder();
for (int i = 0; i < n; i++) {
// If the current character is valid, add it to the result string
if (valid[i])
res.append(s.charAt(i));
}
// Return the final string with invalid parentheses removed
return res.toString();
}
}3. Python Try on Compiler
class Solution:
def minRemoveToMakeValid(self, s):
# Get the length of the input string
n = len(s)
# Stack to track the indices of unmatched opening brackets
st = []
# First pass: Traverse the string to identify unmatched brackets
for i in range(n):
# If the current character is an opening bracket '(', push its index onto the stack
if s[i] == '(':
st.append(i)
# If the current character is a closing bracket ')'
elif s[i] == ')':
# If there's an unmatched opening bracket '(', pop the top of the stack (valid pair found)
if st and s[st[-1]] == '(':
st.pop()
# If no matching opening bracket, push the current closing bracket's index to the stack
else:
st.append(i)
# If the stack is empty, the string is already valid, so return the original string
if not st:
return s
# Create a boolean list valid to mark which characters should be kept (True means valid)
valid = [True] * n
# Mark all indices in the stack as invalid
while st:
valid[st.pop()] = False
# Construct the result string by adding only the valid characters
res = []
for i in range(n):
# If the current character is valid, add it to the result string
if valid[i]:
res.append(s[i])
# Return the final string with invalid parentheses removed
return ''.join(res)
4. Javascript Try on Compiler
var minRemoveToMakeValid = function(s) {
// Get the length of the input string
const n = s.length;
// Stack to track the indices of unmatched opening brackets
const st = [];
// First pass: Traverse the string to identify unmatched brackets
for (let i = 0; i < n; i++) {
// If the current character is an opening bracket '(', push its index onto the stack
if (s[i] === '(')
st.push(i);
// If the current character is a closing bracket ')'
else if (s[i] === ')') {
// If there's an unmatched opening bracket '(', pop the top of the stack (valid pair found)
if (st.length > 0 && s[st[st.length - 1]] === '(')
st.pop();
// If no matching opening bracket, push the current closing bracket's index to the stack
else
st.push(i);
}
}
// If the stack is empty, the string is already valid, so return the original string
if (st.length === 0)
return s;
// Create a boolean array valid to mark which characters should be kept (true means valid)
const valid = new Array(n).fill(true);
// Mark all indices in the stack as invalid
while (st.length > 0) {
valid[st.pop()] = false;
}
// Construct the result string by adding only the valid characters
let res = '';
for (let i = 0; i < n; i++) {
// If the current character is valid, add it to the result string
if (valid[i])
res += s[i];
}
// Return the final string with invalid parentheses removed
return res;
};
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.
We again traversed the string to take only valid characters in our answer, which took the time complexity of O(n).
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 Complexity: O(n)
Explanation: In this solution, the only extra space used is the stack and valid array. 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. Similarly, valid array holds n elements.
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.
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.