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. You need to generate all combinations of balanced parentheses pairs for a given number n. Which algorithmic approach guarantees generating only valid sequences without generating invalid ones first?

easy

A. Brute force: generate all possible sequences of '(' and ')' of length 2n, then filter valid ones

B. Backtracking with pruning: build sequences by adding '(' or ')' only when it keeps the sequence valid

C. Greedy approach: always add '(' until n is reached, then add ')' to close all opened parentheses

D. Dynamic programming: count the number of valid sequences using Catalan number formula

Solution

1. Step 1: Understand problem constraints

   We want to generate all valid parentheses sequences without generating invalid ones first.

2. Step 2: Analyze approaches

   Brute force generates all sequences including invalid ones, greedy fails to generate all valid sequences, DP counts sequences but does not generate them. Backtracking with pruning adds '(' or ')' only when valid, thus generating only valid sequences.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Backtracking with pruning avoids invalid sequences [OK]

Hint: Backtracking prunes invalid sequences early [OK]

Common Mistakes:

• Thinking greedy can generate all valid sequences
• Confusing counting with generating sequences

2. You need to partition a string into substrings such that every substring is a palindrome. Which algorithmic approach guarantees finding all possible palindrome partitions efficiently by pruning invalid partitions early?

easy

A. Backtracking that explores all substring partitions and checks palindrome validity dynamically

B. Dynamic programming that counts the number of palindromic substrings without generating partitions

C. Greedy approach that picks the longest palindrome substring at each step

D. Breadth-first search that generates partitions level by level without palindrome checks

Solution

1. Step 1: Understand problem requirements

   The problem requires generating all palindrome partitions, not just counting or finding one.

2. Step 2: Identify suitable algorithm

   Backtracking explores all partitions and prunes invalid ones by checking palindrome substrings dynamically, ensuring completeness and correctness.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Backtracking with palindrome checks finds all partitions [OK]

Hint: Backtracking explores all partitions with palindrome pruning [OK]

Common Mistakes:

• Assuming greedy longest palindrome picks all partitions
• Confusing counting palindromes with generating partitions
• Ignoring palindrome checks in BFS

3. What is the time complexity of generating all permutations of an array of length n using Heap's algorithm, and why might a common misconception about this complexity be incorrect?

medium

A. O(n! * n^2) because each permutation requires n swaps and there are n! permutations

B. O(n! * log n) because Heap's algorithm uses a heap data structure internally

C. O(n! * n) because each of the n! permutations requires copying the array of length n

D. O(n! + n) because generating permutations is factorial plus linear overhead

Solution

1. Step 1: Identify number of permutations

   There are n! permutations for an array of length n.

2. Step 2: Analyze cost per permutation

   Heap's algorithm generates each permutation with O(1) swaps, but copying the current permutation to the result list takes O(n) time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Time complexity is O(n! * n) due to copying each permutation [OK]

Hint: Copying each permutation costs O(n), not the swaps themselves [OK]

Common Mistakes:

• Assuming swaps cost O(n) each or confusing heap data structure usage

4. Examine the following code snippet for the Word Search II problem. Which line contains a subtle bug that can cause incorrect results or infinite loops?

medium

A. Line: currNode = node.children.get(letter)

B. Line: Missing marking of board[r][c] as visited before recursion

C. Line: if currNode.word:

D. Line: board[r][c] = letter at the end

Solution

1. Step 1: Identify visited marking necessity

   Backtracking requires marking the current cell as visited (e.g., replacing letter with '#') to avoid revisiting the same cell in the current path.

2. Step 2: Locate missing visited marking

   The code lacks the line that marks board[r][c] as visited before recursive calls, causing revisits and potential infinite loops.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Without visited marking, recursion revisits same cells [OK]

Hint: Visited marking prevents revisiting same cell in recursion [OK]

Common Mistakes:

• Forgetting to mark visited cells or unmark after recursion.

5. Suppose the Word Search problem is modified so that the same cell can be used multiple times in forming the word. Which modification to the backtracking algorithm correctly handles this change?

hard

A. Add a global visited set to track cells used in all paths

B. Keep marking visited cells but reset them after each recursion

C. Remove the in-place marking of visited cells to allow reuse

D. Use dynamic programming to store partial results and avoid recomputation

Solution

1. Step 1: Understand new constraint

   Cells can be reused multiple times, so marking visited cells to prevent reuse is no longer needed.

2. Step 2: Modify algorithm accordingly

   Removing in-place marking allows revisiting cells, correctly reflecting the relaxed constraint.

3. Step 3: Evaluate other options

   Keeping marking or using global visited set prevents reuse incorrectly; DP is not suitable here.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Removing visited marking enables cell reuse as required [OK]

Hint: Relaxing constraints often means removing pruning steps [OK]

Common Mistakes:

• Keeping visited marking, causing false negatives
• Adding unnecessary global state