The trick here is to name the state correctly, then let the implementation follow. For 301. Remove Invalid Parentheses, the solution in this repository is mainly a stack solution.
Guide
What?
We want to turn the problem statement into a smaller set of decisions the computer can repeat safely. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: stack, backtracking.
The notes already sitting in the source point us in the right direction:
- backtracking
- 126 / 126 test cases passed, but took too long.
Guide
When?
This pattern shows up when the brute force version has too many repeated checks, too many possible branches, or too much bookkeeping to do by hand. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are valid, backtrack, removeInvalidParentheses.
Guide
Why?
The solution works because it narrows the problem until every update has a clear reason to exist.
- A set is doing the membership or uniqueness work, which keeps the main loop readable.
- The stack stores unfinished context, which is usually the cleanest way to handle nested or monotonic structure.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Read the setup variables first.
- Follow the main loop or recursive helper next.
- Watch where invalid states get skipped.
- Check which value survives to the return statement.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//backtracking
02//126 / 126 test cases passed, but took too long.
03class Solution {
04public:
05 bool valid(const string& expr){
06 stack<char> stk;
07 //open count - close count
08 int balance = 0;
09
10 for(char c : expr){
11 if(c == '('){
12 stk.push(c);
13 ++balance;
14 }else if(c == ')'){
15 if(balance <= 0){
16 //invalid when current close >= open
17 return false;
18 }
19
20 if(!stk.empty() && stk.top() == '('){
21 stk.pop();
22 }else{
23 stk.push(c);
24 }
25 --balance;
26 }else{
27 //skip char that's not parenthesis
28 }
29 }
30
31 return stk.empty();
32 };
33
34 void backtrack(string& s, string& expr, set<string>& exprs, int& minRem, int start, int open, int close, int rem){
35 if(start == s.size()){
36 if(valid(expr)){
37 //update minRem and exprs
38 if(rem < minRem){
39 exprs.clear();
40 minRem = rem;
41 }
42
43 if(rem == minRem){
44 exprs.insert(expr);
45 }
46 }
47 }else if(s[start] != '(' && s[start] != ')'){
48 //for char which is not a parenthesis, directly add it
49 expr += s[start];
50 backtrack(s, expr, exprs, minRem, start+1, open, close, rem);
51 expr.pop_back();
52 }else{
53 /*
54 for s[start] == ')', we should do the pruning here,
55 not at the first layer!
56 o.w. it will fail ")("
57 */
58 if(s[start] == '(' ||
59 (s[start] == ')' && (close < open))){
60 //keep s[start]
61 expr += s[start];
62 backtrack(s, expr, exprs, minRem, start+1, open+(s[start] == '('), close+(s[start]==')'), rem);
63 expr.pop_back();
64 }
65
66 //remove s[start]
67 backtrack(s, expr, exprs, minRem, start+1, open, close, rem+1);
68 }
69 };
70
71 vector<string> removeInvalidParentheses(string s) {
72 string expr = "";
73 set<string> exprs;
74 int minRem = INT_MAX;
75 backtrack(s, expr, exprs, minRem, 0, 0, 0, 0);
76 return vector<string>(exprs.begin(), exprs.end());
77 }
78};
79
80//Approach 1: Backtracking
81//to check if expr is valid, we only need to check if "open == close"!
82//Runtime: 144 ms, faster than 39.89% of C++ online submissions for Remove Invalid Parentheses.
83//Memory Usage: 7.8 MB, less than 82.24% of C++ online submissions for Remove Invalid Parentheses.
84//time: O(2^N), space: O(N)
85class Solution {
86public:
87 void backtrack(string& s, string& expr, set<string>& exprs, int& minRem, int start, int open, int close, int rem){
88 if(start == s.size()){
89 // if(valid(expr)){
90 if(open == close){
91 //update minRem and exprs
92 if(rem < minRem){
93 exprs.clear();
94 minRem = rem;
95 }
96
97 if(rem == minRem){
98 exprs.insert(expr);
99 }
100 }
101 }else if(s[start] != '(' && s[start] != ')'){
102 //for char which is not a parenthesis, directly add it
103 expr += s[start];
104 backtrack(s, expr, exprs, minRem, start+1, open, close, rem);
105 expr.pop_back();
106 }else{
107 /*
108 for s[start] == ')', we should do the pruning here,
109 not at the first layer!
110 o.w. it will fail ")("
111 */
112 if(s[start] == '(' ||
113 (s[start] == ')' && (close < open))){
114 //keep s[start]
115 expr += s[start];
116 backtrack(s, expr, exprs, minRem, start+1, open+(s[start] == '('), close+(s[start]==')'), rem);
117 expr.pop_back();
118 }
119
120 //remove s[start]
121 backtrack(s, expr, exprs, minRem, start+1, open, close, rem+1);
122 }
123 };
124
125 vector<string> removeInvalidParentheses(string s) {
126 string expr = "";
127 set<string> exprs;
128 int minRem = INT_MAX;
129 backtrack(s, expr, exprs, minRem, 0, 0, 0, 0);
130 return vector<string>(exprs.begin(), exprs.end());
131 }
132};
133
134//Approach 2: Limited Backtracking!
135//Runtime: 160 ms, faster than 37.87% of C++ online submissions for Remove Invalid Parentheses.
136//Memory Usage: 7.7 MB, less than 86.24% of C++ online submissions for Remove Invalid Parentheses.
137//time: O(2^N), space: O(N)
138class Solution {
139public:
140 void backtrack(string& s, string& expr, set<string>& exprs, int start, int open, int close, int leftRem, int rightRem){
141 // cout << "start: " << start << ", open: " << open << ", close: " << close << ", leftRem: " << leftRem << ", rightRem: " << rightRem << endl;
142 if(start == s.size()){
143 if(leftRem == 0 && rightRem == 0){
144 exprs.insert(expr);
145 }
146 }else if(s[start] != '(' && s[start] != ')'){
147 expr += s[start];
148 backtrack(s, expr, exprs, start+1, open, close, leftRem, rightRem);
149 expr.pop_back();
150 }else{
151 /*
152 check "(close < open)" in "keep s[start]" part
153 rather than "remove s[start]",
154 o.w. it will fail the case ")("
155 */
156 //keep s[start]
157 if(s[start] == '(' ||
158 (s[start] == ')' && (close < open))){
159 expr += s[start];
160 backtrack(s, expr, exprs, start+1, open+(s[start]=='(') , close+(s[start]==')') , leftRem, rightRem);
161 expr.pop_back();
162 }
163
164 //remove s[start]
165 backtrack(s, expr, exprs, start+1, open, close, leftRem-(s[start]=='('), rightRem-(s[start]==')'));
166 }
167 };
168
169 vector<string> removeInvalidParentheses(string s) {
170 int leftRem = 0, rightRem = 0;
171
172 for(char c : s){
173 if(c == '('){
174 ++leftRem;
175 }else if(c == ')'){
176 if(leftRem > 0){
177 /*
178 match current closing parenthesis to
179 previous opening parenthesis
180 */
181 --leftRem;
182 }else{
183 //leftRem == 0
184 /*
185 this means we cannot match
186 current closing parenthesis to
187 any opening parenthesis,
188 so current closing parenthesis should be removed
189 */
190 ++rightRem;
191 }
192 }
193 }
194
195 // cout << "leftRem: " << leftRem << ", rightRem: " << rightRem << endl;
196
197 string expr = "";
198 set<string> exprs;
199 backtrack(s, expr, exprs, 0, 0, 0, leftRem, rightRem);
200
201 return vector<string>(exprs.begin(), exprs.end());
202 }
203};Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.