Remove Invalid Parentheses

📋

Problem

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.

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 ')'.

Edge cases: Empty string → returns [""]String with no parentheses → returns the string itselfString with all valid parentheses → returns the string itself

</>

IDE

def remove_invalid_parentheses(s: str) -> list:public List<String> removeInvalidParentheses(String s)vector<string> removeInvalidParentheses(string s)function removeInvalidParentheses(s)

def remove_invalid_parentheses(s: str) -> list:
    # Write your solution here
    pass

class Solution {
    public List<String> removeInvalidParentheses(String s) {
        // Write your solution here
        return new ArrayList<>();
    }
}

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

vector<string> removeInvalidParentheses(string s) {
    // Write your solution here
    return {};
}

function removeInvalidParentheses(s) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: ()())()Returned input string without removing invalid parentheses; failed to find minimal removals.✅ Implement BFS or backtracking to remove invalid parentheses and check validity at each step.

Wrong: ()()()Returned only one valid string due to greedy removal of first invalid parenthesis.✅ Use BFS level-by-level to find all minimal removals and collect all valid strings at that level.

Wrong: Returned empty list on empty input or string without parentheses.✅ Return [""] for empty input and [input] if no parentheses present.

Wrong: (((((Failed to remove invalid parentheses when all are invalid.✅ Remove all invalid parentheses and return [""] if none remain valid.

Wrong: (())())()Removed parentheses multiple times or failed to prune duplicates.✅ Track indices of removals and prune duplicate states in recursion or BFS.

✓

Test Cases

Focus on handling empty and trivial inputs correctly before tackling edge cases.

Understand common pitfalls like greedy removal and duplicate pruning to handle corner cases.

Optimize your algorithm to handle large inputs efficiently using BFS and pruning.

t1_01basic

Input{"s":"()())()"}

Expected["()()()","(())()"]

⏱ Performance - must finish in 2000ms

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

💡 Think about removing the minimum number of parentheses to balance the string.

💡 Use BFS or backtracking to generate all possible removals level by level.

💡 Stop at the first level where valid strings are found to ensure minimum removals.

Why it failed: Returned invalid strings or missed valid minimal removals. Fix by ensuring BFS stops at first valid level and collects all valid strings at that level.

✓ Correct minimal removals and all valid strings returned.

t1_02basic

Input{"s":"(a)())()"}

Expected["(a)()()","(a())()"]

⏱ Performance - must finish in 2000ms

Similar to canonical example but with letters; minimal removals yield two valid strings.

💡 Letters do not affect validity; only parentheses count.

💡 Check validity by counting parentheses ignoring letters.

💡 Apply BFS or backtracking similarly to find minimal removals.

Why it failed: Incorrectly removed letters or failed to consider letters as valid characters. Fix by only removing parentheses and ignoring letters in validity checks.

✓ Correctly handled letters and minimal removals.

t2_01edge

Input{"s":""}

Expected[""]

⏱ Performance - must finish in 2000ms

Empty string is valid; return list with empty string.

💡 Empty input should return itself as valid.

💡 Check if your code handles empty strings without error.

💡 Return [""] immediately if input is empty.

Why it failed: Returned empty list or error on empty input. Fix by handling empty input as valid and returning [""] directly.

✓ Correctly returns [""] for empty input.

t2_02edge

Input{"s":"abcde"}

Expected["abcde"]

⏱ Performance - must finish in 2000ms

String with no parentheses is already valid; return itself.

💡 If no parentheses, string is valid by default.

💡 Check validity function ignores letters correctly.

💡 Return original string in a list if no removals needed.

Why it failed: Incorrectly removed letters or returned empty list. Fix by skipping removal when no parentheses present.

✓ Correctly returns original string when no parentheses.

t2_03edge

Input{"s":"()()"}

Expected["()()"]

⏱ Performance - must finish in 2000ms

String with all valid parentheses; no removals needed.

💡 Check if input is already valid before removals.

💡 Avoid unnecessary removals if string is valid.

💡 Return input string in a list if valid.

Why it failed: Removed valid parentheses unnecessarily. Fix by validating input first and returning early if valid.

✓ Correctly returns input when already valid.

t3_01corner

Input{"s":"((((("}

Expected[""]

⏱ Performance - must finish in 2000ms

All parentheses are invalid; minimal removal is removing all to get empty string.

💡 Check if your code handles strings with only invalid '(' correctly.

💡 Minimal removal means removing all invalid parentheses.

💡 Return [""] when no valid parentheses remain.

Why it failed: Returned non-empty strings with invalid parentheses. Fix by removing all invalid parentheses and returning empty string if none valid.

✓ Correctly returns [""] when all parentheses are invalid.

t3_02corner

Input{"s":"()())())"}

Expected["()()()","(())()"]

⏱ Performance - must finish in 2000ms

Tests greedy trap: removing first invalid ')' only may miss other valid minimal removals.

💡 Greedy removal of first invalid parenthesis may miss other solutions.

💡 Use BFS level-by-level to find all minimal removals.

💡 Collect all valid strings at first valid removal level.

Why it failed: Returned only one valid string due to greedy removal. Fix by using BFS to explore all minimal removals at same level.

✓ Correctly returns all minimal valid strings.

t3_03corner

Input{"s":"(())())()"}

Expected["(())()()","(())()()"]

⏱ Performance - must finish in 2000ms

Tests confusion between 0/1 and unbounded removals; only remove each parenthesis once.

💡 Each parenthesis can be removed at most once.

💡 Avoid removing the same parenthesis multiple times in recursion.

💡 Use indices to track removals and avoid duplicates.

Why it failed: Removed same parenthesis multiple times causing duplicates or invalid results. Fix by tracking indices and pruning duplicates.

✓ Correctly handles 0/1 removal per parenthesis.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this"}

Expectednull

⏱ Performance - must finish in 2000ms

Input length n=100000; solution must run in O(n * 2^k) where k is minimal removals, optimized BFS or pruning required.

💡 Brute force exponential solutions will time out on large inputs.

💡 Use BFS with pruning and early stopping at first valid level.

💡 Avoid generating all subsequences; prune invalid paths early.

Why it failed: TLE due to exponential brute force without pruning. Fix by implementing BFS level-by-level with pruning and early stopping.

✓ Solution runs within time limit using BFS pruning.

Practice

1. 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

2. Consider the following buggy code for generating letter combinations. Which line contains the subtle bug that causes incorrect or incomplete results?

from collections import deque

def letterCombinations(digits):
    if digits == '':
        return ['']
    digit_map = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
                 '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
    queue = deque([''])
    for digit in digits:
        letters = digit_map[digit]
        for _ in range(len(queue)):
            prev = queue.popleft()
            for char in letters:
                queue.append(prev + char)
    return list(queue)

medium

A. Line 7: letters = digit_map[digit]

B. Line 2: if digits == '': return ['']

C. Line 10: prev = queue.popleft()

D. Line 1: from collections import deque

Solution

1. Step 1: Analyze empty input handling

   Returning [''] for empty input is incorrect; the problem expects an empty list [] when input is empty.

2. Step 2: Check other lines

   Digit mapping, queue operations, and imports are correct and do not cause bugs.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Empty input should return [] not [''] to match problem spec [OK]

Hint: Empty input must return empty list, not list with empty string [OK]

Common Mistakes:

• Returning [''] instead of [] for empty input
• Assuming digits '1' or '0' map to letters

3. What is the time complexity of the bitmask-optimized backtracking solution for the N-Queens problem, and why is the common misconception that it is O(n^3) incorrect?

medium

A. O(n^3) because there are three nested loops over rows, columns, and diagonals

B. O(2^n) because bitmasking iterates over all subsets of columns

C. O(n!) because each row places one queen and pruning reduces the search space factorially

D. O(n^2) because each queen placement checks all previous rows and columns

Solution

1. Step 1: Identify the branching factor per row

   Each row places exactly one queen, and pruning avoids invalid columns and diagonals, reducing choices drastically.

2. Step 2: Understand factorial growth

   Because queens cannot share columns, the number of ways to place queens is at most n!; pruning reduces this further but worst-case remains O(n!).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Bitmask pruning reduces search to permutations of columns [OK]

Hint: N-Queens search space is permutations, not polynomial loops [OK]

Common Mistakes:

• Assuming nested loops imply cubic time
• Confusing bitmask subsets with full subsets
• Ignoring pruning effect

4. Identify the bug in the following code snippet for getPermutation:

medium

A. Line 6: k is not converted to zero-based index before calculations.

B. Line 2: factorial array initialization is incorrect.

C. Line 10: The index calculation uses integer division incorrectly.

D. Line 12: numbers.pop(idx) should be numbers.remove(idx).

Solution

1. Step 1: Check k adjustment

   k must be decremented by 1 to convert to zero-based indexing before using factorial divisions.

2. Step 2: Understand impact of missing k -= 1

   Without this, idx calculation is off by one, leading to incorrect permutation output.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing k -= 1 causes wrong indexing and wrong permutation [OK]

Hint: Always convert k to zero-based before factorial indexing [OK]

Common Mistakes:

• Forgetting zero-based index adjustment
• Misusing pop vs remove
• Incorrect factorial initialization

5. The following code attempts to generate all permutations of a list using Heap's algorithm but contains a subtle bug:

def permute(nums):
    res = [nums[:]]
    c = [0] * len(nums)
    i = 0
    while i < len(nums):
        if c[i] < i:
            if i % 2 == 0:
                nums[0], nums[i] = nums[i], nums[0]
            else:
                nums[c[i]], nums[i] = nums[i], nums[c[i]]
            res.append(nums)
            c[i] += 1
            i = 0
        else:
            c[i] = 0
            i += 1
    return res

What is the bug in this code?

medium

A. The used array c is not reset properly, causing infinite loop

B. Appending nums directly without copying causes all entries in res to reference the same list

C. Swapping nums[0] and nums[i] when i is even is incorrect logic

D. The initial res list should be empty, not contain nums[:] at start

Solution

1. Step 1: Identify how results are stored

   The code appends nums directly to res without copying.

2. Step 2: Understand consequences of appending references

   Since nums is mutated in-place, all entries in res point to the same list, resulting in duplicates of the final permutation.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Appending a copy nums[:] fixes the bug [OK]

Hint: Always append a copy of mutable lists to results [OK]

Common Mistakes:

• Forgetting to copy before appending results in duplicate references