Remove Invalid Parentheses

🎯

Remove Invalid Parentheses

hardBACKTRACKINGFacebookAmazonGoogle

Imagine you receive a corrupted string of parentheses from a user input or a legacy system, and you need to clean it up by removing the minimum number of invalid parentheses to make it valid again.

💡 This problem requires exploring all possible ways to remove invalid parentheses to restore validity. Beginners often struggle because the solution requires careful pruning and understanding of what makes a parentheses string valid, and brute force can be overwhelming without pruning.

📋

Problem Statement

Given a string s that contains parentheses and letters, remove the minimum number of invalid parentheses to make the input string valid. Return all possible results in any order. A string is valid if parentheses are balanced and properly closed.

1 ≤ s.length ≤ 10^5s consists of lowercase English letters and parentheses '(' and ')'.

💡

Example

Input"()())()"

Output["()()()", "(())()"]

Removing one invalid ')' at different positions yields two valid strings.

Input"(a)())()"

Output["(a)()()", "(a())()"]

Letters are ignored in validity checks; removing one invalid ')' yields two valid strings.

Input")("

Output[""]

No valid parentheses can be formed, so empty string is the only valid result.

• Empty string → returns [""]
• String with no parentheses → returns the string itself
• String with all valid parentheses → returns the string itself
• String with only invalid parentheses → returns [""]

⚠️

Common Mistakes

Not pruning early when parentheses count is invalid

Excessive recursion or BFS states causing TLE

✅ Add checks to prune paths where closing parentheses exceed opening ones

Not handling duplicates leading to repeated results

Output contains duplicates, or performance degrades due to repeated states

✅ Use a set or hash map to track visited strings or results

Adding ')' when it would invalidate the string (more ')' than '(')

Generates invalid strings, increasing search space

✅ Only add ')' if rightCount < leftCount during backtracking

Removing characters other than parentheses

Incorrect results or missing valid strings

✅ Only remove '(' or ')' characters during generation

🧠

Brute Force (Generate All Subsequences and Check Validity)

💡 This approach exists to build foundational understanding by exploring all possible removals, showing why pruning and optimization are necessary.

Intuition

Try removing every possible combination of parentheses and check if the resulting string is valid. Collect all valid strings with minimum removals.

Algorithm

1. Generate all possible subsequences by removing parentheses in all combinations.
2. Check each subsequence for validity of parentheses.
3. Track the minimum number of removals needed to get a valid string.
4. Return all valid strings with minimum removals.

💡 The brute force approach is hard because the number of subsequences grows exponentially, and checking validity repeatedly is costly.

</>

Code

from typing import List

def is_valid(s: str) -> bool:
    count = 0
    for c in s:
        if c == '(': count += 1
        elif c == ')':
            count -= 1
            if count < 0:
                return False
    return count == 0

def remove_invalid_parentheses(s: str) -> List[str]:
    res = []
    min_removed = float('inf')

    def backtrack(index: int, path: str, removed: int):
        nonlocal min_removed
        if index == len(s):
            if is_valid(path):
                if removed < min_removed:
                    min_removed = removed
                    res.clear()
                    res.append(path)
                elif removed == min_removed:
                    res.append(path)
            return

        # Option 1: remove current char if it's a parenthesis
        if s[index] in ('(', ')'):
            backtrack(index + 1, path, removed + 1)

        # Option 2: keep current char
        backtrack(index + 1, path + s[index], removed)

    backtrack(0, "", 0)
    return res

# Driver code
if __name__ == "__main__":
    test_str = "()())()"
    print(remove_invalid_parentheses(test_str))

Line Notes

def is_valid(s: str) -> bool:Defines a helper to check if parentheses are balanced

if count < 0:Early exit if closing parenthesis exceeds opening ones

def backtrack(index: int, path: str, removed: int):Recursive function exploring all subsequences

if removed < min_removed:Update minimum removals and reset results when better found

import java.util.*;

public class RemoveInvalidParentheses {
    public static boolean isValid(String s) {
        int count = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') count++;
            else if (c == ')') {
                count--;
                if (count < 0) return false;
            }
        }
        return count == 0;
    }

    public static List<String> removeInvalidParentheses(String s) {
        List<String> res = new ArrayList<>();
        int[] minRemoved = {Integer.MAX_VALUE};

        backtrack(s, 0, new StringBuilder(), 0, minRemoved, res);
        return res;
    }

    private static void backtrack(String s, int index, StringBuilder path, int removed, int[] minRemoved, List<String> res) {
        if (index == s.length()) {
            if (isValid(path.toString())) {
                if (removed < minRemoved[0]) {
                    minRemoved[0] = removed;
                    res.clear();
                    res.add(path.toString());
                } else if (removed == minRemoved[0]) {
                    res.add(path.toString());
                }
            }
            return;
        }

        char c = s.charAt(index);
        if (c == '(' || c == ')') {
            backtrack(s, index + 1, path, removed + 1, minRemoved, res);
        }

        path.append(c);
        backtrack(s, index + 1, path, removed, minRemoved, res);
        path.deleteCharAt(path.length() - 1);
    }

    public static void main(String[] args) {
        String test = "()())()";
        System.out.println(removeInvalidParentheses(test));
    }
}

Line Notes

public static boolean isValid(String s)Helper to check balanced parentheses

if (count < 0) return false;Early invalid detection to prune

backtrack(s, index + 1, path, removed + 1, minRemoved, res);Try removing current parenthesis

path.deleteCharAt(path.length() - 1);Backtrack by removing last added char

#include <iostream>
#include <vector>
#include <string>
#include <climits>
using namespace std;

bool isValid(const string& s) {
    int count = 0;
    for (char c : s) {
        if (c == '(') count++;
        else if (c == ')') {
            count--;
            if (count < 0) return false;
        }
    }
    return count == 0;
}

void backtrack(const string& s, int index, string& path, int removed, int& minRemoved, vector<string>& res) {
    if (index == (int)s.size()) {
        if (isValid(path)) {
            if (removed < minRemoved) {
                minRemoved = removed;
                res.clear();
                res.push_back(path);
            } else if (removed == minRemoved) {
                res.push_back(path);
            }
        }
        return;
    }

    if (s[index] == '(' || s[index] == ')') {
        backtrack(s, index + 1, path, removed + 1, minRemoved, res);
    }

    path.push_back(s[index]);
    backtrack(s, index + 1, path, removed, minRemoved, res);
    path.pop_back();
}

vector<string> removeInvalidParentheses(string s) {
    vector<string> res;
    int minRemoved = INT_MAX;
    string path;
    backtrack(s, 0, path, 0, minRemoved, res);
    return res;
}

int main() {
    string test = "()())()";
    vector<string> result = removeInvalidParentheses(test);
    for (auto& str : result) {
        cout << str << endl;
    }
    return 0;
}

Line Notes

bool isValid(const string& s)Checks if parentheses are balanced

if (count < 0) return false;Detect invalid early to avoid unnecessary work

backtrack(s, index + 1, path, removed + 1, minRemoved, res);Try removing current parenthesis

path.pop_back();Undo last addition to explore other paths

function isValid(s) {
    let count = 0;
    for (let c of s) {
        if (c === '(') count++;
        else if (c === ')') {
            count--;
            if (count < 0) return false;
        }
    }
    return count === 0;
}

function removeInvalidParentheses(s) {
    const res = [];
    let minRemoved = Infinity;

    function backtrack(index, path, removed) {
        if (index === s.length) {
            if (isValid(path)) {
                if (removed < minRemoved) {
                    minRemoved = removed;
                    res.length = 0;
                    res.push(path);
                } else if (removed === minRemoved) {
                    res.push(path);
                }
            }
            return;
        }

        if (s[index] === '(' || s[index] === ')') {
            backtrack(index + 1, path, removed + 1);
        }

        backtrack(index + 1, path + s[index], removed);
    }

    backtrack(0, "", 0);
    return res;
}

// Test
console.log(removeInvalidParentheses("()())()"));

Line Notes

function isValid(s)Checks if parentheses are balanced

if (count < 0) return false;Early invalid detection to prune search

backtrack(index + 1, path, removed + 1);Try removing current parenthesis

res.length = 0;Clear previous results when better minimum found

⏱

Complexity

TimeO(2^n * n)

SpaceO(n) recursion stack + O(2^n) result storage

We explore all subsequences (2^n) and check validity (O(n)) for each, leading to exponential time.

💡 For n=10, this means roughly 1024 subsequences to check, which is already slow; for n=20, over a million, so this approach is impractical for large inputs.

Interview Verdict: TLE / Use only to introduce problem complexity

This approach is too slow for large inputs but is essential to understand the problem's search space and motivate pruning.

🧠

Backtracking with Pruning and Early Validity Checks

💡 This approach improves brute force by pruning invalid paths early and avoiding duplicate work, making it feasible for moderate input sizes.

Intuition

Use backtracking to remove parentheses only when necessary, track counts of left and right parentheses removed, and prune paths that cannot lead to valid strings.

Algorithm

1. Calculate the minimum number of left and right parentheses to remove.
2. Use backtracking to try removing parentheses only when needed.
3. Keep track of counts of parentheses to ensure validity during construction.
4. Avoid duplicates by skipping consecutive identical parentheses removals.

💡 The key difficulty is managing counts and pruning to avoid exponential blowup and duplicates.

</>

Code

from typing import List

def remove_invalid_parentheses(s: str) -> List[str]:
    res = set()

    # Calculate minimum removals
    left_remove, right_remove = 0, 0
    for c in s:
        if c == '(': left_remove += 1
        elif c == ')':
            if left_remove > 0:
                left_remove -= 1
            else:
                right_remove += 1

    def backtrack(index: int, path: str, left_count: int, right_count: int, left_remove: int, right_remove: int):
        if index == len(s):
            if left_remove == 0 and right_remove == 0:
                res.add(path)
            return

        c = s[index]

        if c == '(' and left_remove > 0:
            backtrack(index + 1, path, left_count, right_count, left_remove - 1, right_remove)

        elif c == ')' and right_remove > 0:
            backtrack(index + 1, path, left_count, right_count, left_remove, right_remove - 1)

        # Keep current char
        if c not in ('(', ')'):
            backtrack(index + 1, path + c, left_count, right_count, left_remove, right_remove)
        elif c == '(':  # add '('
            backtrack(index + 1, path + c, left_count + 1, right_count, left_remove, right_remove)
        elif c == ')' and right_count < left_count:  # add ')' only if valid
            backtrack(index + 1, path + c, left_count, right_count + 1, left_remove, right_remove)

    backtrack(0, "", 0, 0, left_remove, right_remove)
    return list(res)

# Driver code
if __name__ == "__main__":
    test_str = "()())()"
    print(remove_invalid_parentheses(test_str))

Line Notes

left_remove, right_remove = 0, 0Count minimum parentheses to remove to fix imbalance

if left_remove > 0:Try removing '(' only if we have removals left

if c not in ('(', ')'):Always keep non-parenthesis characters

elif c == ')' and right_count < left_count:Add ')' only if it won't invalidate string

import java.util.*;

public class RemoveInvalidParentheses {
    public static List<String> removeInvalidParentheses(String s) {
        Set<String> res = new HashSet<>();
        int leftRemove = 0, rightRemove = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') leftRemove++;
            else if (c == ')') {
                if (leftRemove > 0) leftRemove--;
                else rightRemove++;
            }
        }

        backtrack(s, 0, new StringBuilder(), 0, 0, leftRemove, rightRemove, res);
        return new ArrayList<>(res);
    }

    private static void backtrack(String s, int index, StringBuilder path, int leftCount, int rightCount, int leftRemove, int rightRemove, Set<String> res) {
        if (index == s.length()) {
            if (leftRemove == 0 && rightRemove == 0) {
                res.add(path.toString());
            }
            return;
        }

        char c = s.charAt(index);

        if (c == '(' && leftRemove > 0) {
            backtrack(s, index + 1, path, leftCount, rightCount, leftRemove - 1, rightRemove, res);
        } else if (c == ')' && rightRemove > 0) {
            backtrack(s, index + 1, path, leftCount, rightCount, leftRemove, rightRemove - 1, res);
        }

        path.append(c);

        if (c != '(' && c != ')') {
            backtrack(s, index + 1, path, leftCount, rightCount, leftRemove, rightRemove, res);
        } else if (c == '(') {
            backtrack(s, index + 1, path, leftCount + 1, rightCount, leftRemove, rightRemove, res);
        } else if (c == ')' && rightCount < leftCount) {
            backtrack(s, index + 1, path, leftCount, rightCount + 1, leftRemove, rightRemove, res);
        }

        path.deleteCharAt(path.length() - 1);
    }

    public static void main(String[] args) {
        String test = "()())()";
        System.out.println(removeInvalidParentheses(test));
    }
}

Line Notes

int leftRemove = 0, rightRemove = 0;Calculate minimum removals needed

if (c == '(' && leftRemove > 0)Try removing '(' only if needed

path.append(c);Add current character to path before recursion

path.deleteCharAt(path.length() - 1);Backtrack by removing last character

#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
using namespace std;

void backtrack(const string& s, int index, string& path, int leftCount, int rightCount, int leftRemove, int rightRemove, unordered_set<string>& res) {
    if (index == (int)s.size()) {
        if (leftRemove == 0 && rightRemove == 0) {
            res.insert(path);
        }
        return;
    }

    char c = s[index];

    if (c == '(' && leftRemove > 0) {
        backtrack(s, index + 1, path, leftCount, rightCount, leftRemove - 1, rightRemove, res);
    } else if (c == ')' && rightRemove > 0) {
        backtrack(s, index + 1, path, leftCount, rightCount, leftRemove, rightRemove - 1, res);
    }

    path.push_back(c);

    if (c != '(' && c != ')') {
        backtrack(s, index + 1, path, leftCount, rightCount, leftRemove, rightRemove, res);
    } else if (c == '(') {
        backtrack(s, index + 1, path, leftCount + 1, rightCount, leftRemove, rightRemove, res);
    } else if (c == ')' && rightCount < leftCount) {
        backtrack(s, index + 1, path, leftCount, rightCount + 1, leftRemove, rightRemove, res);
    }

    path.pop_back();
}

vector<string> removeInvalidParentheses(string s) {
    int leftRemove = 0, rightRemove = 0;
    for (char c : s) {
        if (c == '(') leftRemove++;
        else if (c == ')') {
            if (leftRemove > 0) leftRemove--;
            else rightRemove++;
        }
    }

    unordered_set<string> res;
    string path;
    backtrack(s, 0, path, 0, 0, leftRemove, rightRemove, res);
    return vector<string>(res.begin(), res.end());
}

int main() {
    string test = "()())()";
    vector<string> result = removeInvalidParentheses(test);
    for (auto& str : result) {
        cout << str << endl;
    }
    return 0;
}

Line Notes

int leftRemove = 0, rightRemove = 0;Count minimum parentheses to remove

if (c == '(' && leftRemove > 0)Try removing '(' only if removal quota remains

path.push_back(c);Add character before recursive call

path.pop_back();Backtrack to explore other options

function removeInvalidParentheses(s) {
    let leftRemove = 0, rightRemove = 0;
    for (let c of s) {
        if (c === '(') leftRemove++;
        else if (c === ')') {
            if (leftRemove > 0) leftRemove--;
            else rightRemove++;
        }
    }

    const res = new Set();

    function backtrack(index, path, leftCount, rightCount, leftRemove, rightRemove) {
        if (index === s.length) {
            if (leftRemove === 0 && rightRemove === 0) {
                res.add(path);
            }
            return;
        }

        const c = s[index];

        if (c === '(' && leftRemove > 0) {
            backtrack(index + 1, path, leftCount, rightCount, leftRemove - 1, rightRemove);
        } else if (c === ')' && rightRemove > 0) {
            backtrack(index + 1, path, leftCount, rightCount, leftRemove, rightRemove - 1);
        }

        if (c !== '(' && c !== ')') {
            backtrack(index + 1, path + c, leftCount, rightCount, leftRemove, rightRemove);
        } else if (c === '(') {
            backtrack(index + 1, path + c, leftCount + 1, rightCount, leftRemove, rightRemove);
        } else if (c === ')' && rightCount < leftCount) {
            backtrack(index + 1, path + c, leftCount, rightCount + 1, leftRemove, rightRemove);
        }
    }

    backtrack(0, "", 0, 0, leftRemove, rightRemove);
    return Array.from(res);
}

// Test
console.log(removeInvalidParentheses("()())()"));

Line Notes

let leftRemove = 0, rightRemove = 0;Calculate minimum removals needed

if (c === '(' && leftRemove > 0)Try removing '(' only if quota remains

res.add(path);Add valid string to results set to avoid duplicates

backtrack(index + 1, path + c, leftCount + 1, rightCount, leftRemove, rightRemove);Add '(' and update count

⏱

Complexity

TimeO(2^n)

SpaceO(n) recursion stack + O(2^n) result storage

Pruning reduces the search space compared to brute force, but worst case remains exponential.

💡 For n=20, pruning helps but still may explore many paths; practical for interview but not huge inputs.

Interview Verdict: Accepted / Practical for interviews

This approach balances clarity and efficiency, making it a good coding choice in interviews.

🧠

Breadth-First Search (BFS) Level-by-Level Removal

💡 This approach uses BFS to find the shortest removal sequence, guaranteeing minimum removals and avoiding deep recursion.

Intuition

Start from the original string and generate all strings by removing one parenthesis at a time. Use BFS to explore level by level until valid strings are found.

Algorithm

1. Initialize a queue with the original string and a visited set.
2. While queue not empty, process all strings at current level.
3. For each string, check if valid; if yes, add to results and stop further deeper levels.
4. If not valid, generate all possible strings by removing one parenthesis and enqueue unseen ones.
5. Return all valid strings found at the first valid level.

💡 The BFS ensures minimal removals by exploring all strings with fewer removals before more.

</>

Code

from typing import List
from collections import deque

def is_valid(s: str) -> bool:
    count = 0
    for c in s:
        if c == '(': count += 1
        elif c == ')':
            count -= 1
            if count < 0:
                return False
    return count == 0

def remove_invalid_parentheses_bfs(s: str) -> List[str]:
    res = []
    visited = set([s])
    queue = deque([s])
    found = False

    while queue:
        size = len(queue)
        for _ in range(size):
            curr = queue.popleft()
            if is_valid(curr):
                res.append(curr)
                found = True
            if found:
                continue
            for i in range(len(curr)):
                if curr[i] not in ('(', ')'):
                    continue
                next_str = curr[:i] + curr[i+1:]
                if next_str not in visited:
                    visited.add(next_str)
                    queue.append(next_str)
        if found:
            break
    return res

# Driver code
if __name__ == "__main__":
    test_str = "()())()"
    print(remove_invalid_parentheses_bfs(test_str))

Line Notes

visited = set([s])Track visited strings to avoid repeats

if is_valid(curr):Check if current string is valid parentheses

for i in range(len(curr))Try removing each parenthesis once

if found: breakStop BFS once valid strings found at current level

import java.util.*;

public class RemoveInvalidParentheses {
    public static boolean isValid(String s) {
        int count = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') count++;
            else if (c == ')') {
                count--;
                if (count < 0) return false;
            }
        }
        return count == 0;
    }

    public static List<String> removeInvalidParenthesesBFS(String s) {
        List<String> res = new ArrayList<>();
        Set<String> visited = new HashSet<>();
        Queue<String> queue = new LinkedList<>();
        visited.add(s);
        queue.offer(s);
        boolean found = false;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String curr = queue.poll();
                if (isValid(curr)) {
                    res.add(curr);
                    found = true;
                }
                if (found) continue;

                for (int j = 0; j < curr.length(); j++) {
                    if (curr.charAt(j) != '(' && curr.charAt(j) != ')') continue;
                    String next = curr.substring(0, j) + curr.substring(j + 1);
                    if (!visited.contains(next)) {
                        visited.add(next);
                        queue.offer(next);
                    }
                }
            }
            if (found) break;
        }
        return res;
    }

    public static void main(String[] args) {
        String test = "()())()";
        System.out.println(removeInvalidParenthesesBFS(test));
    }
}

Line Notes

Set<String> visited = new HashSet<>();Avoid revisiting same strings

if (isValid(curr)) {Check validity at current BFS level

for (int j = 0; j < curr.length(); j++) {Generate next states by removing one parenthesis

if (found) break;Stop BFS after first valid level

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <unordered_set>
using namespace std;

bool isValid(const string& s) {
    int count = 0;
    for (char c : s) {
        if (c == '(') count++;
        else if (c == ')') {
            count--;
            if (count < 0) return false;
        }
    }
    return count == 0;
}

vector<string> removeInvalidParenthesesBFS(string s) {
    vector<string> res;
    unordered_set<string> visited;
    queue<string> q;
    visited.insert(s);
    q.push(s);
    bool found = false;

    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            string curr = q.front(); q.pop();
            if (isValid(curr)) {
                res.push_back(curr);
                found = true;
            }
            if (found) continue;

            for (int j = 0; j < (int)curr.size(); j++) {
                if (curr[j] != '(' && curr[j] != ')') continue;
                string next = curr.substr(0, j) + curr.substr(j + 1);
                if (visited.find(next) == visited.end()) {
                    visited.insert(next);
                    q.push(next);
                }
            }
        }
        if (found) break;
    }
    return res;
}

int main() {
    string test = "()())()";
    vector<string> result = removeInvalidParenthesesBFS(test);
    for (auto& str : result) {
        cout << str << endl;
    }
    return 0;
}

Line Notes

unordered_set<string> visited;Track visited strings to prevent repeats

if (isValid(curr)) {Check if current string is valid

for (int j = 0; j < (int)curr.size(); j++) {Generate next states by removing one parenthesis

if (found) break;Stop BFS after finding valid strings at current level

function isValid(s) {
    let count = 0;
    for (let c of s) {
        if (c === '(') count++;
        else if (c === ')') {
            count--;
            if (count < 0) return false;
        }
    }
    return count === 0;
}

function removeInvalidParenthesesBFS(s) {
    const res = [];
    const visited = new Set([s]);
    const queue = [s];
    let found = false;

    while (queue.length > 0) {
        const size = queue.length;
        for (let i = 0; i < size; i++) {
            const curr = queue.shift();
            if (isValid(curr)) {
                res.push(curr);
                found = true;
            }
            if (found) continue;

            for (let j = 0; j < curr.length; j++) {
                if (curr[j] !== '(' && curr[j] !== ')') continue;
                const next = curr.slice(0, j) + curr.slice(j + 1);
                if (!visited.has(next)) {
                    visited.add(next);
                    queue.push(next);
                }
            }
        }
        if (found) break;
    }
    return res;
}

// Test
console.log(removeInvalidParenthesesBFS("()())()"));

Line Notes

const visited = new Set([s]);Track visited strings to avoid duplicates

if (isValid(curr)) {Check if current string is valid parentheses

for (let j = 0; j < curr.length; j++) {Generate next states by removing one parenthesis

if (found) break;Stop BFS after first valid level to ensure minimal removals

⏱

Complexity

TimeO(n * 2^n)

SpaceO(2^n)

BFS explores all strings with increasing removals until valid strings found; each string generation is O(n).

💡 For small to medium n, BFS is efficient and guarantees minimal removals; for large n, exponential growth remains a challenge.

Interview Verdict: Accepted / Optimal for minimal removals

BFS is often the best approach to guarantee minimal removals and avoid deep recursion, making it ideal for interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, approach 2 (backtracking with pruning) or approach 3 (BFS) are best to code. Brute force is only for explanation.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^n * n)	O(n) recursion + O(2^n) results	Yes	Yes	Mention only - never code
2. Backtracking with Pruning	O(2^n) worst, often better due to pruning	O(n) recursion + O(2^n) results	Possible	Yes	Good choice to code
3. BFS Level-by-Level	O(n * 2^n)	O(2^n)	No	Yes	Optimal approach, good to mention or code

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain brute force to show complexity, followed by pruning or BFS approaches for efficiency.

How to Present

Step 1: Clarify input, output, and what makes a string valid.Step 2: Present brute force to show the exponential search space.Step 3: Introduce pruning with backtracking to reduce search space.Step 4: Explain BFS to guarantee minimal removals and avoid recursion depth.Step 5: Code the pruning or BFS approach depending on time.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 15min → Test: 3min. Total ~25min

What the Interviewer Tests

Interviewer tests your understanding of parentheses validity, ability to prune search space, and knowledge of BFS vs DFS tradeoffs.

Common Follow-ups

• How to handle duplicates efficiently → Use sets or hash maps to avoid repeated states.
• Can you optimize space usage → Use iterative BFS with pruning or iterative DFS with memoization.

💡 These follow-ups test your ability to optimize and handle edge cases beyond the base solution.

🔍

Pattern Recognition

When to Use

1) Need to remove minimum invalid characters 2) Result must be all valid strings 3) Input is a string with parentheses 4) Problem involves exploring many combinations

Signature Phrases

remove minimum number of invalid parenthesesreturn all possible valid strings

NOT This Pattern When

Problems that only check validity without removals or that ask for counting valid strings without generating them.

Similar Problems

Generate Parentheses - generating all valid parentheses stringsLongest Valid Parentheses - finding longest valid substringValid Parentheses - checking if a string is valid