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

Practice

1. Given the following code for generating unique permutations, what is the final output when the input is [1,1,2]?

from typing import List

def permuteUnique(nums: List[int]) -> List[List[int]]:
    nums.sort()
    res = []
    def backtrack(start=0):
        if start == len(nums):
            res.append(nums[:])
            return
        seen = set()
        for i in range(start, len(nums)):
            if nums[i] in seen:
                continue
            seen.add(nums[i])
            nums[start], nums[i] = nums[i], nums[start]
            backtrack(start + 1)
            nums[start], nums[i] = nums[i], nums[start]
    backtrack()
    return res

print(permuteUnique([1,1,2]))

easy

A. [[1,2,1],[1,1,2],[2,1,1]]

B. [[1,1,2],[2,1,1],[1,2,1]]

C. [[1,1,2],[1,2,1],[2,1,1]]

D. [[2,1,1],[1,1,2],[1,2,1]]

Solution

1. Step 1: Trace initial sorting and first level of recursion

   Input sorted to [1,1,2]. At start=0, i iterates over 0 to 2. First, swap nums[0] with nums[0] (1), add 1 to seen, recurse.

2. Step 2: Trace subsequent recursion and skipping duplicates

   At start=1, i iterates 1 to 2. Swap nums[1] with nums[1] (1), add 1 to seen, recurse. Then swap nums[2] with nums[1] (2), add 2 to seen, recurse. Duplicate 1 at i=2 skipped due to seen.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches expected unique permutations in lex order [OK]

Hint: Sort input and skip duplicates with seen set [OK]

Common Mistakes:

• Misordering output permutations due to swap order

2. What is the time complexity of the optimal backtracking solution that generates all valid parentheses sequences for input n?

medium

A. O(2^{2n} * n) because it generates all sequences and checks validity

B. O(n^2) because it builds sequences of length 2n with nested loops

C. O(n!) because it permutes parentheses positions

D. O(\frac{4^n}{n^{3/2}}) because the number of valid sequences is the nth Catalan number

Solution

1. Step 1: Identify number of valid sequences

   The number of valid parentheses sequences is the nth Catalan number, approximately 4^n / (n^{3/2}).

2. Step 2: Analyze backtracking time

   Backtracking generates all valid sequences, so time is proportional to number of sequences times sequence length, which is O(4^n / n^{3/2} * n) = O(4^n / n^{1/2}).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Matches known Catalan number growth for valid parentheses [OK]

Hint: Catalan number growth dominates complexity [OK]

Common Mistakes:

• Confusing brute force with backtracking complexity
• Assuming factorial complexity

3. What is the time complexity of the optimal iterative approach using a queue to generate all letter combinations for a digit string of length n, assuming each digit maps to at most 4 letters?

medium

A. O(n * 4^n) because we process each digit and expand combinations exponentially

B. O(2^n) because each digit doubles the number of combinations

C. O(4^n * n) because there are up to 4^n combinations and each combination is built with n concatenations

D. O(n^2) because we process n digits and each combination takes n steps

Solution

1. Step 1: Identify number of combinations

   Each digit maps to up to 4 letters, so total combinations are up to 4^n.

2. Step 2: Analyze work per combination

   Each combination is built by concatenating letters for n digits, so each combination requires O(n) time to build.

3. Step 3: Simplify complexity expression

   O(4^n * n) and O(n * 4^n) are equivalent; however, O(n * 4^n) because we process each digit and expand combinations exponentially is the standard notation emphasizing processing each digit and expanding combinations exponentially.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Time is exponential in n with linear cost per combination [OK]

Hint: Exponential combinations times linear build cost [OK]

Common Mistakes:

• Confusing exponential base (2 vs 4)
• Ignoring concatenation cost per combination

4. What is the time complexity of the optimal backtracking algorithm that generates unique permutations of an array with duplicates by sorting and skipping duplicates during recursion?

medium

A. O(n! * log n) due to sorting and binary search for duplicates

B. O(n! * n^2) because each permutation requires copying the array and checking duplicates

C. O(n^n) because the recursion explores all possible swaps without pruning

D. O(n! * n) because pruning duplicates early reduces redundant branches but each permutation still requires O(n) copying

Solution

1. Step 1: Identify complexity of outer and inner loops

   Backtracking explores permutations, which is O(n!). Each permutation requires copying O(n) elements to result.

2. Step 2: Check if pruning duplicates reduces complexity

   Pruning duplicates early avoids redundant branches, so complexity is O(n! * n), not worse. Sorting is O(n log n) but done once.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Pruning reduces branches but copying each permutation costs O(n) [OK]

Hint: Pruning duplicates reduces branches but copying costs O(n) per permutation [OK]

Common Mistakes:

• Confusing pruning effect or ignoring copy cost

5. Suppose the problem changes so that each element in the input array can be used multiple times in each permutation (i.e., unlimited reuse). Which modification to the backtracking algorithm correctly generates all unique permutations with duplicates allowed and reuse permitted?

hard

A. Use backtracking without swapping, but at each recursion level, iterate over all elements and skip duplicates using a 'used' boolean array to avoid repeated elements at the same recursion depth.

B. Remove the 'seen' set and allow swapping elements freely without skipping duplicates.

C. Sort the array and use the same swapping and 'seen' set logic as before, but do not increment the recursion start index to allow reuse.

D. Generate all permutations without sorting or skipping duplicates, then filter duplicates at the end using a hash set.

Solution

1. Step 1: Understand reuse requirement

   Unlimited reuse means elements can be chosen multiple times at each recursion level, so swapping and incrementing start index is not suitable.

2. Step 2: Identify correct approach

   Backtracking without swapping, iterating over all elements at each recursion level, and using a 'used' boolean array to skip duplicates at the same depth ensures unique permutations with reuse.

3. Step 3: Evaluate other options

   Removing 'seen' causes duplicates; swapping without incrementing start index breaks logic; filtering duplicates after generation is inefficient.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Backtracking with reuse requires iteration over all elements each recursion, not swapping with start index increment [OK]

Hint: Reuse requires iteration over all elements each recursion, not swapping with start index increment [OK]

Common Mistakes:

• Trying to reuse elements by swapping without adjusting recursion index or skipping duplicates properly