Log inSign up
hardLeetCodeNot Started

Remove Invalid Parentheses

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Backtracking
Solve on LeetCode
Lesson

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 the unique results in any order.

A string is valid if: 1. Open parentheses are closed by matching close parentheses. 2. Open parentheses are closed in the correct order. 3. Every close parenthesis has a preceding matching open parenthesis. 4. Non-parenthesis characters remain unchanged in their relative order.

Example 1:

Input: s = "()())()"
Output: ["(())()", "()()()"]
Explanation: Removing the single invalid ")" at index 1, 3, or 4 produces the two unique minimal valid strings.

Example 2:

Input: s = "(a)())()"
Output: ["(a())()", "(a)()()"]
Explanation: Minimal removal count is 1 ")". Letters like "a" are kept in place.

Example 3:

Input: s = ")("
Output: [""]
Explanation: Both brackets are invalid; removing both gives the empty string "".

Constraints:

  • 1 <= s.length <= 25
  • s consists of lowercase English letters and parentheses ( and )
  • There will be at most 20 parentheses in s

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand how to precompute search bounds to avoid exploring suboptimal branches in backtracking.
  • Master consecutive duplicate element suppression in string deletion problems.
  • Compare BFS vs DFS trade-offs for minimum transformation distance problems.

1. Breadth-First Search (BFS) Level by Level

Intuition

Maintain a visited set and a queue. For each popped string, if valid, collect it and set found = true. Otherwise, if not found yet, generate all candidate substrings by deleting one parenthesis and enqueue them.

Algorithm

  1. Step 1: Generate all 2N possible sub-sequences by removing subsets of characters.
  2. Step 2: Filter the generated strings to retain only valid parentheses expressions.
  3. Step 3: Keep strings of maximum length (minimum removals) and remove duplicates using a Set.
  4. Step 4: Return result list.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <queue>
5#include <unordered_set>
6
7class Solution {
8public:
9 bool isValid(const std::string& s) {
10 int count = 0;
11 for (char c : s) {
12 if (c == '(') count++;
13 else if (c == ')') {
14 count--;
15 if (count < 0) return false;
16 }
17 }
18 return count == 0;
19 }
20
21 std::vector<std::string> removeInvalidParentheses(std::string s) {
22 std::vector<std::string> result;
23 std::unordered_set<std::string> visited;
24 std::queue<std::string> q;
25
26 q.push(s);
27 visited.insert(s);
28 bool found = false;
29
30 while (!q.empty()) {
31 int sz = q.size();
32 for (int k = 0; k < sz; k++) {
33 std::string curr = q.front();
34 q.pop();
35
36 if (isValid(curr)) {
37 result.push_back(curr);
38 found = true;
39 }
40
41 if (found) continue;
42
43 for (int i = 0; i < (int)curr.length(); i++) {
44 if (curr[i] != '(' && curr[i] != ')') continue;
45 std::string next = curr.substr(0, i) + curr.substr(i + 1);
46 if (!visited.count(next)) {
47 visited.insert(next);
48 q.push(next);
49 }
50 }
51 }
52 if (found) break;
53 }
54 return result;
55 }
56};
57
58int main() {
59 Solution solver;
60 std::vector<std::string> res = solver.removeInvalidParentheses("()())()");
61 std::cout << "BFS Output for '()())()':\n";
62 for (const auto& str : res) {
63 std::cout << "\"" << str << "\"\n";
64 }
65 return 0;
66}

Time & Space Complexity

  • Time complexity: O(2^N * N) — Explores levels until minimum removal depth is reached.
  • Space complexity: O(2^N * N) — The BFS queue and visited set store up to O(2N) substrings.

2. DFS Backtracking with Misplaced Character Counters

Intuition

A linear pass counts misplaced open and close brackets. DFS removes brackets only at indices where removal matches the budget, skipping duplicate sibling removals (if (i > index && s[i] == s[i-1]) continue).

Algorithm

  1. Step 1: Use BFS with a Queue initialized with the original string s.
  2. Step 2: Maintain a visited set to avoid processing duplicate strings.
  3. Step 3: At each level, check if any string in the queue is valid.
  4. Step 4: If valid strings are found at current level, collect them all and stop generating further levels.
  5. Step 5: If not found, generate the next level by removing one bracket at each index.
  6. Step 6: Return all valid strings from the shortest removal level.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <unordered_set>
5
6class Solution {
7public:
8 bool isValid(const std::string& s) {
9 int count = 0;
10 for (char c : s) {
11 if (c == '(') count++;
12 else if (c == ')') {
13 count--;
14 if (count < 0) return false;
15 }
16 }
17 return count == 0;
18 }
19
20 void dfs(const std::string& s, int index, int remL, int remR, std::unordered_set<std::string>& result) {
21 if (remL == 0 && remR == 0) {
22 if (isValid(s)) result.insert(s);
23 return;
24 }
25 for (int i = index; i < (int)s.length(); i++) {
26 if (i > index && s[i] == s[i - 1]) continue;
27 if (remR > 0 && s[i] == ')') {
28 dfs(s.substr(0, i) + s.substr(i + 1), i, remL, remR - 1, result);
29 } else if (remL > 0 && s[i] == '(') {
30 dfs(s.substr(0, i) + s.substr(i + 1), i, remL - 1, remR, result);
31 }
32 }
33 }
34
35 std::vector<std::string> removeInvalidParentheses(std::string s) {
36 int remL = 0, remR = 0;
37 for (char c : s) {
38 if (c == '(') remL++;
39 else if (c == ')') {
40 if (remL > 0) remL--;
41 else remR++;
42 }
43 }
44 std::unordered_set<std::string> result;
45 dfs(s, 0, remL, remR, result);
46 return std::vector<std::string>(result.begin(), result.end());
47 }
48};
49
50int main() {
51 Solution solver;
52 std::vector<std::string> res = solver.removeInvalidParentheses("()())()");
53 std::cout << "DFS Counter Output for '()())()':\n";
54 for (const auto& str : res) {
55 std::cout << "\"" << str << "\"\n";
56 }
57 return 0;
58}

Time & Space Complexity

  • Time complexity: O(2^N) — Searches strictly down to depth equal to total misplaced count.
  • Space complexity: O(N) — O(N) recursion stack depth.

3. Two-Pass Prefix Balance Backtracking (No Set Required)

Intuition

By deleting invalid close brackets in the first pass and invalid open brackets on the reversed string in the second pass, the algorithm avoids any Hash Set lookups and produces unique valid strings directly.

Algorithm

  1. Step 1: Count misplaced open (() and close ()) brackets upfront in O(N): remL and remR.
  2. Step 2: Define backtrack(index, leftCount, rightCount, remL, remR, current).
  3. Step 3: Prune immediately: if rightCount > leftCount, branch is invalid; return.
  4. Step 4: Removal choices: if s[i] == ( and remL > 0, explore removal branch; if s[i] == ) and remR > 0, explore removal branch.
  5. Step 5: Skip duplicate removals: if s[i] == s[i-1] and previous was not removed, skip.
  6. Step 6: Keep choice: append s[i] to current and recurse.
  7. Step 7: Base case: if index == s.length and remL == 0 and remR == 0 and leftCount == rightCount, add current to result.

Misplaced Bracket Pruned DFS Trace

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
Precompute misplaced counts: scan '()())()'
Visual state
Values and pointers at this exact step
tree
Root
remL: 0, remR: 1

Node order shown; add connections to display explicit tree edges.

Variables at this step
remL
0
remR
1
current
Check / comparison
remL = 0, remR = 1 (exactly 1 close bracket to remove)
Decision / next transition
Start DFS with budget remL = 0, remR = 1
Why this step matters

Precompute misplaced counts: scan ()())(). remL = 0, remR = 1 (one excess ) must be removed).

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5
6class Solution {
7public:
8 void removeHelper(std::string s, int iStart, int jStart, char openP, char closeP, std::vector<std::string>& result) {
9 int numOpen = 0, numClose = 0;
10 for (int i = iStart; i < (int)s.length(); i++) {
11 if (s[i] == openP) numOpen++;
12 if (s[i] == closeP) numClose++;
13 if (numClose > numOpen) {
14 for (int j = jStart; j <= i; j++) {
15 if (s[j] == closeP && (j == jStart || s[j - 1] != closeP)) {
16 removeHelper(s.substr(0, j) + s.substr(j + 1), i, j, openP, closeP, result);
17 }
18 }
19 return;
20 }
21 }
22 std::string reversed = s;
23 std::reverse(reversed.begin(), reversed.end());
24 if (openP == '(') {
25 removeHelper(reversed, 0, 0, ')', '(', result);
26 } else {
27 result.push_back(reversed);
28 }
29 }
30
31 std::vector<std::string> removeInvalidParentheses(std::string s) {
32 std::vector<std::string> result;
33 removeHelper(s, 0, 0, '(', ')', result);
34 return result;
35 }
36};
37
38int main() {
39 Solution solver;
40 std::vector<std::string> res = solver.removeInvalidParentheses("()())()");
41 std::cout << "Optimal Two-Pass Output for '()())()':\n";
42 for (const auto& str : res) {
43 std::cout << "\"" << str << "\"\n";
44 }
45 return 0;
46}

Time & Space Complexity

  • Time complexity: O(2^k * N) — Branches strictly on mismatched brackets, executing in linear time relative to valid outputs.
  • Space complexity: O(N) — O(N) recursion stack memory with 0 auxiliary sets.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Breadth-First Search (BFS)O(2^N * N)O(2^N * N)Queue memory blows up exponentially on wide trees.
2.DFS with Misplaced Counting (Better)O(2^N)O(N)Requires visited set or validation check at leaf nodes.
3.Two-Pass Prefix Balance Backtracking (Optimal)OptimalO(2^k * N)O(N)Requires understanding two-pass string reversal symmetry.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Deleting non-parenthesis alphabetic characters. Ensure letters (a-z) are skipped and preserved in place during bracket deletion checks.

Pitfall 2:

Generating duplicates by removing from identical consecutive parentheses. Only delete the first parenthesis in a consecutive duplicate run (if (j == jStart || s[j-1] != closeP)).

Crucial Edge Cases to Validate:

  • Already valid string (e.g. (a)()) -> returns [(a)()].
  • Completely invalid string (e.g. )() -> removes both brackets, returns [''].
  • No parentheses, only characters (e.g. abc) -> returns [abc].
  • All open brackets (e.g. ((() -> removes all 3, returns [''].

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Highlight the precomputation step remLeft and remRight first before writing any DFS recursive function.
  2. Explain how skipping adjacent duplicates avoids placing identical strings into hash sets.
  3. Present the two-pass string reversal algorithm if the interviewer asks for zero memory allocation beyond the call stack.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is BFS or precomputed counter DFS required instead of standard greedy removal?

Back to DSA Sheet