Bird
Raised Fist0
Interview PrepbacktrackinghardFacebookAmazonGoogle

Remove Invalid Parentheses

Choose your preparation mode4 modes available

Start learning this pattern below

Jump into concepts and practice - no test required

or
Recommended
Test this pattern10 questions across easy, medium, and hard to know if this pattern is strong
📋
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
}
0/9
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
t1_01basic
Input{"s":"()())()"}
Expected["()()()","(())()"]

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

t1_02basic
Input{"s":"(a)())()"}
Expected["(a)()()","(a())()"]

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

t2_01edge
Input{"s":""}
Expected[""]

Empty string is valid; return list with empty string.

t2_02edge
Input{"s":"abcde"}
Expected["abcde"]

String with no parentheses is already valid; return itself.

t2_03edge
Input{"s":"()()"}
Expected["()()"]

String with all valid parentheses; no removals needed.

t3_01corner
Input{"s":"((((("}
Expected[""]

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

t3_02corner
Input{"s":"()())())"}
Expected["()()()","(())()"]

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

t3_03corner
Input{"s":"(())())()"}
Expected["(())()()","(())()()"]

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

t4_01performance
Input{"_description":"n=100000 at constraint boundary - executor generates this"}
⏱ 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.

Practice

(1/5)
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