Minimum Remove to Make Valid Parentheses solution and explanation
Google
9 more videos on this problem
Minimum Remove to Make Valid Parentheses - Leetcode 1249 - PythonNeetCodeIO · 14:43 · 36K views
LeetCode 1249. Minimum Remove to Make Valid ParenthesesNick White · 8:57 · 34K views
1249. Minimum Remove to Make Valid Parentheses | Stack | 4 waysAryan Mittal · 38:59 · 3K views
Minimum Remove to Make Valid Parentheses - LeetCode 1249 - Python #leetcode #string #stackDeepti Talesra · 11:21 · 2K views
Leetcode 1249 Minimum Remove to Make Valid ParenthesesRen Zhang · 10:34 · 1K views
Minimum Remove to Make Valid Parentheses | Leetcode 1249Coding Decoded · 10:15 · 1K views
Leetcode 1249. Minimum remove to make valid parentheses - Balanced Brackets Ep5InterviewDose · 12:58 · 1K views
1249. Minimum Remove to Make Valid Parentheses - LeetCode JavaScriptBecoming A Better Dev (with David) · 8:17 · 321 views
Minimum Remove to Make Valid Parentheses - Stack - Facebook Interview Question - Leetcode 1249CheatCode Ninja · 5:24 · 316 views
1249. Minimum Remove to Make Valid Parentheses || Leetcode Medium || Most Optimised SolutionKomal Pal · 11:46 · 228 views
The problem
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(Aconcatenated withB), whereAandBare valid strings, or - It can be written as
(A), whereAis a valid string.
Example 1:
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.
Example 2:
Input: s = "a)b(c)d" Output: "ab(c)d"
Example 3:
Input: s = "))(("
Output: ""
Explanation: An empty string is also valid.
Constraints:
1 <= s.length <= 105s[i]is either'(',')', or lowercase English letter.
Approach overview
Problem Overview: You receive a string containing lowercase letters and parentheses. The goal is to remove the minimum number of characters so the remaining parentheses form a valid expression. A valid string means every opening ( has a matching closing ) in the correct order.
Approach 1: Two-Pass String Traversal with Index Tracking (Time: O(n), Space: O(n))
This method scans the string twice to filter invalid parentheses. During the first pass, iterate left to right and track the balance of open parentheses. Append characters to a temporary result but skip any closing parenthesis ) that does not have a matching open. This guarantees that the intermediate string never has excess closing brackets.
The second pass runs right to left to remove extra opening parentheses. Track remaining unmatched ( and skip them when building the final string. Using two passes ensures both imbalance cases are handled cleanly without complex bookkeeping. This approach relies purely on string traversal and counters, making it easy to implement when working with string processing problems.
Approach 2: Single-Pass Efficient Stack Solution (Time: O(n), Space: O(n))
The stack-based method records indices of unmatched parentheses while iterating once through the string. Push the index of every ( onto a stack. When encountering ), check the stack: if an opening parenthesis exists, pop it to form a valid pair; otherwise record the index of the invalid closing parenthesis.
After traversal, any remaining indices in the stack correspond to unmatched opening parentheses. Combine these with invalid closing indices and remove those positions from the string. The final string contains only valid pairs. This approach is common in parentheses validation problems because the stack directly models the nesting structure of expressions.
Recommended for interviews: The single-pass stack approach is the one most interviewers expect. It demonstrates clear understanding of parenthesis matching using a LIFO structure and maintains linear time complexity. The two-pass traversal is also strong because it avoids extra index bookkeeping and shows clean reasoning about invalid cases. Mentioning both approaches shows depth: one focuses on stack mechanics, the other on careful string filtering.
Approach 1: Two-Pass String Traversal with Index Tracking
This approach involves performing two passes over the string. In the first pass, traverse the string to identify unmatched closing parentheses and their indices. In the second pass, traverse from right to left to identify unmatched opening parentheses. This process allows removing these indices to yield a balanced parentheses string.
def minRemoveToMakeValid(s: str) -> str:
stack = []
s = list(s)
for i, char in enumerate(s):
if char == '(':
stack.append(i)
elif char == ')':
if stack:
stack.pop()
else:
s[i] = ''
for i in stack:
s[i] = ''
return ''.join(s)import java.util.Stack;
public class Solution {
public String minRemoveToMakeValid(String s) {
Stack<Integer> stack = new Stack<>();
StringBuilder sb = new StringBuilder(s);
for (int i = 0; i < sb.length(); i++) {
if (sb.charAt(i) == '(') {
stack.push(i);
} else if (sb.charAt(i) == ')') {
if (!stack.isEmpty()) {
stack.pop();
} else {
sb.setCharAt(i, '*');
}
}
}
while (!stack.isEmpty()) {
sb.setCharAt(stack.pop(), '*');
}
return sb.toString().replaceAll("\\*", "");
}
}#include <iostream>
#include <string>
#include <stack>
using namespace std;
string minRemoveToMakeValid(string s) {
stack<int> stack;
string result = s;
for (int i = 0; i < s.length(); ++i) {
if (s[i] == '(') stack.push(i);
else if (s[i] == ')') {
if (!stack.empty()) stack.pop();
else result[i] = '*';
}
}
while (!stack.empty()) {
result[stack.top()] = '*';
stack.pop();
}
result.erase(remove(result.begin(), result.end(), '*'), result.end());
return result;
}function minRemoveToMakeValid(s) {
const stack = [];
s = s.split('');
for (let i = 0; i < s.length; i++) {
if (s[i] === '(') {
stack.push(i);
} else if (s[i] === ')') {
if (stack.length > 0) {
stack.pop();
} else {
s[i] = '';
}
}
}
while (stack.length > 0) {
s[stack.pop()] = '';
}
return s.join('');
}#include <stdio.h>
#include <string.h>
#include <stdlib.h>
char* minRemoveToMakeValid(char* s) {
int i, balance = 0, len = strlen(s);
char* result = (char*)malloc(len + 1);
char* builder = (char*)malloc(len + 1);
int j = 0;
// First pass: remove extra closing brackets
for (i = 0; i < len; ++i) {
if (s[i] == '(') {
balance++;
} else if (s[i] == ')') {
if (balance == 0) continue;
balance--;
}
builder[j++] = s[i];
}
builder[j] = '\0';
balance = 0;
j = 0;
// Second pass: remove extra opening brackets from the end
for (i = strlen(builder) - 1; i >= 0; --i) {
if (builder[i] == ')') {
balance++;
} else if (builder[i] == '(') {
if (balance == 0) continue;
balance--;
}
result[j++] = builder[i];
}
result[j] = '\0';
// Reverse the result to get final valid string
for (i = 0; i < j / 2; ++i) {
char tmp = result[i];
result[i] = result[j - i - 1];
result[j - i - 1] = tmp;
}
free(builder);
return result;
}using System;
using System.Text;
using System.Collections.Generic;
public class Solution {
public string MinRemoveToMakeValid(string s) {
Stack<int> stack = new Stack<int>();
StringBuilder sb = new StringBuilder(s);
for (int i = 0; i < sb.Length; i++) {
if (sb[i] == '(') stack.Push(i);
else if (sb[i] == ')') {
if (stack.Count == 0) {
sb[i] = '*';
} else {
stack.Pop();
}
}
}
while (stack.Count > 0) {
sb[stack.Pop()] = '*';
}
return sb.ToString().Replace("*", "");
}
}This method uses list mutation to mark invalid parentheses with empty strings. A stack is used to keep track of unmatched opening brackets.
Time Complexity: O(n), each character is iterated through at most twice.
Space Complexity: O(n), with n for both stack tracking and storing the index changes.
Approach 2: Single-Pass Efficient Stack Solution
This strategy employs a single-pass solution with a stack to track the indices of unmatched parentheses. Upon completing the pass, these tracked indices inform which characters can remain in the final valid string output. This approach saves memory by avoiding additional passes over the string.
def minRemoveToMakeValid(s: str) -> str:
stack = []
s = list(s)
for i, char in enumerate(s):
if char == '(':
stack.append(i)
elif char == ')':
if stack:
stack.pop()
else:
s[i] = ''
while stack:
s[stack.pop()] = ''
return ''.join(s)import java.util.Stack;
public class Solution {
public String minRemoveToMakeValid(String s) {
Stack<Integer> stack = new Stack<>();
char[] arr = s.toCharArray();
for (int i = 0; i < arr.length; i++) {
if (arr[i] == '(') stack.push(i);
else if (arr[i] == ')') {
if (!stack.isEmpty()) stack.pop();
else arr[i] = '*';
}
}
while (!stack.isEmpty()) arr[stack.pop()] = '*';
StringBuilder sb = new StringBuilder();
for (char c : arr) {
if (c != '*') sb.append(c);
}
return sb.toString();
}
}#include <iostream>
#include <string>
#include <stack>
using namespace std;
string minRemoveToMakeValid(string s) {
stack<int> stack;
for (int i = 0; i < s.length(); ++i) {
if (s[i] == '(') stack.push(i);
else if (s[i] == ')') {
if (!stack.empty()) stack.pop();
else s[i] = '*';
}
}
while (!stack.empty()) {
s[stack.top()] = '*';
stack.pop();
}
s.erase(remove(s.begin(), s.end(), '*'), s.end());
return s;
}function minRemoveToMakeValid(s) {
const stack = [];
s = s.split('');
for (let i = 0; i < s.length; i++) {
if (s[i] === '(') {
stack.push(i);
} else if (s[i] === ')') {
if (stack.length > 0) {
stack.pop();
} else {
s[i] = '';
}
}
}
while (stack.length > 0) {
s[stack.pop()] = '';
}
return s.join('');
}#include <stdio.h>
#include <string.h>
#include <stdlib.h>
char* minRemoveToMakeValid(char* s) {
int i, top = -1, len = strlen(s);
int* stack = (int*)malloc(len * sizeof(int));
char* result = (char*)malloc(len + 1);
for (i = 0; i < len; ++i) {
if (s[i] == '(') stack[++top] = i;
else if (s[i] == ')') {
if (top != -1) top--;
else s[i] = '.'; // marker for invalid parenthesis
}
}
while (top != -1) s[stack[top--]] = '.';
int j = 0;
for (i = 0; i < len; ++i) {
if (s[i] != '.') result[j++] = s[i];
}
result[j] = '\0';
free(stack);
return result;
}using System;
using System.Text;
using System.Collections.Generic;
public class Solution {
public string MinRemoveToMakeValid(string s) {
Stack<int> stack = new Stack<int>();
char[] arr = s.ToCharArray();
for (int i = 0; i < arr.Length; i++) {
if (arr[i] == '(') stack.Push(i);
else if (arr[i] == ')') {
if (stack.Count == 0) {
arr[i] = '*';
} else {
stack.Pop();
}
}
}
while (stack.Count > 0) {
arr[stack.Pop()] = '*';
}
StringBuilder sb = new StringBuilder();
foreach (char c in arr) {
if (c != '*') sb.Append(c);
}
return sb.ToString();
}
}Employing native list capabilities, Python uses position tracking alongside efficient string mutations which keep the operation linear and memory aware.
Time Complexity: O(n), mandates a linear runtime for the prospected length of the initial string.
Space Complexity: O(n), requiring interim storage correspondingly.
Approach 3: Two Passes
First, we scan from left to right and remove the extra right parentheses. Then, we scan from right to left and remove the extra left parentheses.
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the string s.
Similar problems:
function minRemoveToMakeValid(s: string): string {
let left = 0;
let right = 0;
for (const c of s) {
if (c === '(') {
left++;
} else if (c === ')') {
if (right < left) {
right++;
}
}
}
let hasLeft = 0;
let res = '';
for (const c of s) {
if (c === '(') {
if (hasLeft < right) {
hasLeft++;
res += c;
}
} else if (c === ')') {
if (hasLeft != 0 && right !== 0) {
right--;
hasLeft--;
res += c;
}
} else {
res += c;
}
}
return res;
}func minRemoveToMakeValid(s string) string {
stk := []byte{}
x := 0
for i := range s {
c := s[i]
if c == ')' && x == 0 {
continue
}
if c == '(' {
x++
} else if c == ')' {
x--
}
stk = append(stk, c)
}
ans := []byte{}
x = 0
for i := len(stk) - 1; i >= 0; i-- {
c := stk[i]
if c == '(' && x == 0 {
continue
}
if c == ')' {
x++
} else if c == '(' {
x--
}
ans = append(ans, c)
}
for i, j := 0, len(ans)-1; i < j; i, j = i+1, j-1 {
ans[i], ans[j] = ans[j], ans[i]
}
return string(ans)
}impl Solution {
pub fn min_remove_to_make_valid(s: String) -> String {
let bs = s.as_bytes();
let mut right = {
let mut left = 0;
let mut right = 0;
for c in bs.iter() {
match c {
&b'(' => {
left += 1;
}
&b')' if right < left => {
right += 1;
}
_ => {}
}
}
right
};
let mut has_left = 0;
let mut res = vec![];
for c in bs.iter() {
match c {
&b'(' => {
if has_left < right {
has_left += 1;
res.push(*c);
}
}
&b')' => {
if has_left != 0 && right != 0 {
right -= 1;
has_left -= 1;
res.push(*c);
}
}
_ => {
res.push(*c);
}
}
}
String::from_utf8_lossy(&res).to_string()
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Two-Pass String Traversal with Index Tracking | Time Complexity: O(n), each character is iterated through at most twice. |
| Single-Pass Efficient Stack Solution | Time Complexity: O(n), mandates a linear runtime for the prospected length of the initial string. |
| Two Passes | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pass String Traversal with Index Tracking | O(n) | O(n) | When you prefer simple logic using counters and sequential scans without managing a stack |
| Single-Pass Efficient Stack Solution | O(n) | O(n) | Best general approach for parenthesis validation and matching problems |
Frequently asked questions
Is Minimum Remove to Make Valid Parentheses easy or hard?
The problem is rated Medium because it combines string processing with stack logic. The algorithm itself is linear, but handling invalid indices and reconstructing the string correctly requires careful implementation.
Minimum Remove to Make Valid Parentheses Python/Java solution
Python and Java implementations typically follow the stack approach. Iterate through the string, push indices of '(' onto the stack, and track unmatched ')'. After the pass, remove all invalid indices and rebuild the string. Both languages achieve O(n) time and O(n) space complexity.
How to solve Minimum Remove to Make Valid Parentheses in O(n)?
Traverse the string while tracking unmatched parentheses. With the stack method, push indices of '(' and remove invalid ')'. After traversal, remove any remaining indices stored in the stack. Another O(n) approach performs two passes: first remove extra closing parentheses, then remove extra opening ones.
What is the best approach for Minimum Remove to Make Valid Parentheses?
The most common solution uses a stack to track indices of unmatched parentheses while scanning the string once. Each '(' index is pushed onto the stack, and matching ')' pops it. Any remaining indices represent invalid characters that should be removed. This method runs in O(n) time with O(n) space.
Is Minimum Remove to Make Valid Parentheses asked at Google/Amazon/Meta?
Parentheses validation and expression-cleaning problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants include Valid Parentheses, Remove Invalid Parentheses, and Minimum Remove to Make Valid Parentheses, all testing stack usage and string traversal skills.
What data structure is used in Minimum Remove to Make Valid Parentheses?
A stack is the primary data structure because it naturally models nested parentheses. It stores indices of opening brackets and allows constant-time matching when a closing bracket appears. Some solutions also use arrays or sets to mark invalid indices before rebuilding the string.
What is the time complexity of Minimum Remove to Make Valid Parentheses?
Optimal solutions run in O(n) time because the string is processed with a single or double linear scan. Each character is visited at most twice. Space complexity is O(n) when storing indices of invalid parentheses or building the result string.