# 3ms C++ Solution, preprocessing but simple recursion

• This problem takes me quite a long time. But I finally made it work. My approach is based on observation that an invalid string is either due to extra ')' or extra '('. For example, "( ) ) ) ( )" contains extra ')', and "( ) ( ( ( ) " contains extra '('. So an invalid string is either a ')'-invalid substring, or a '('-invalid substring, or a mixture of two. If an invalid string contains both, then it can be divided into three parts [ ')'-invalid substring ] + [valid substring] + [ '('-invalid substring ]. In addition, [ ')'-invalid substring ] can never interleave with [ '('-invalid substring ], because extra '(' will always be offset by extra ')'. With this in mind, we can divide the original string into three parts, ')'-invalid substring, valid substring, and '('-invalid substring. In addition, we should keep the number of extra ')' and the number of extra '('. Now, we can just run DFS to delete these extra ')' and '('.

Edits: some more explanations

Here, I provide my code:

``````public:
vector<string> removeInvalidParentheses(string s) {
vector<string> result;
if(s.empty()) return vector<string>(1, "");
while(!s.empty() && s[0] == ')') s.erase(0, 1); // deleting leading ')'
while(!s.empty() && s.back() == '(') s.pop_back(); // deleting trailing '('
int leftEnd = -1; // last character of left_invalid_str
int rightStart = s.size(); // First character of right_invalid_str
int leftNb = 0, rightNb = 0; // Record the number of extra ')' or '('
for(int i = 0; i < s.size(); i++) { // With rightStart, we do not need a stack.
if(isalpha(s[i])) continue;
if(s[i] == '(') {
if(rightStart == s.size()) rightStart = i;
rightNb++;
}
else if(rightNb) {
if(rightNb == 1) rightStart = s.size();
rightNb--;
}
else {
leftEnd = i;
leftNb++;
}
}
string goodStr = s.substr(leftEnd + 1, rightStart - leftEnd - 1);
string leftStr = s.substr(0, leftEnd + 1);
string rightStr = s.substr(rightStart);
unordered_set<string> arrLeft, arrRight;
string leftPath = "", rightPath = "";
dfs(arrLeft, leftNb, leftStr, 0, leftPath, false, 0);
dfs(arrRight, rightNb, rightStr, 0, rightPath, true, 0);
for(auto& l : arrLeft)
for(auto& r : arrRight)
result.push_back(l + goodStr + r);
return result;
}

private:
void dfs(unordered_set<string>& result, int invNb, string& str, int pos, string& path, bool isRev, int p) {
if(invNb == 0) {
int temp = pos;
for(int temp = pos; temp < str.size(); temp++) {
if(str[temp] == '(') p++;
else if(str[temp] == ')') p--;
if(p < 0) return;
}
if(p == 0) result.insert(path + str.substr(pos));
return;
}
if(pos == str.size() || p<0) return;
char validCh = isRev ? ')' : '(';
if(str[pos] == validCh || isalpha(str[pos])) {
if(str[pos] == '(') p++;
else if(str[pos] == ')') p--;
path += str[pos];
dfs(result, invNb, str, pos + 1, path, isRev, p);
path.pop_back();
}
else {
dfs(result, invNb - 1, str, pos + 1, path, isRev, p); // abandon
if(isRev) ++p;
else --p;
path += str[pos];
dfs(result, invNb, str, pos + 1, path, isRev, p); // not abandon
path.pop_back();
}
}
```			i. Preprocessing, deleting leading ')' on left side, and deleting trailing '(' on right side
ii. Dividing the preprocessed string, s, into three parts: leftStr + goodStr, rightStr
1) leftStr start from the left end of s, it only contains extra ')'
2) rightStr start from the right end of s, it only contains extra '('
3) goodStr is a substring of s that has neither extra ')' nor extra '('.
4) We can use an explicit stack or implicit stack to record the end of leftStr, the beginning of rightStr, and number of extra ')' in leftStr, leftNb, and the number of extra '(' in rightStr, rightNb
iii. Now we run DFS with backtracking to delete extra ')' in leftStr, and delete extra '(' in rightStr
1) A tricky point is that we must use a variable to indicate whether a partial solution is valid or not. We use an integer p
2) Every time we append a '(' in the partial solution, p++
3) Every time we append a ')' in the partial solution, p--
4) When p < 0, we know that the partial solution is invalid, we stop the DFS.			i. Preprocessing, deleting leading ')' on left side, and deleting trailing '(' on right side
ii. Dividing the preprocessed string, s, into three substrings (in sequence): leftStr + goodStr + rightStr
1) leftStr: starting from the left end of s, it only contains extra ')'
2) rightStr starting from the right end of s, it only contains extra '('
3) goodStr is a substring of s that has neither extra ')' nor extra '('.
4) This partition operation can be realized by using an explicit stack or implicit stack to record the end of leftStr, the beginning of rightStr, and number of extra ')' in leftStr, and the number of extra '(' in rightStr.
iii. Now we run DFS with backtracking to delete extra ')' in leftStr, and delete extra '(' in rightStr
1) A tricky point is that we must use a variable to indicate whether a partial solution is valid or not. So, we keep an integer p = 0. This is also an implicit stack technique.
2) Every time we append a '(' in the partial solution, p++
3) Every time we append a ')' in the partial solution, p--
4) When p < 0, we know that the partial solution is invalid, we stop the DFS.			i. Preprocessing, deleting leading ')' on left side, and deleting trailing '(' on right side
ii. Dividing the preprocessed string, s, into three substrings (in sequence): leftStr + goodStr + rightStr
1) leftStr: starting from the left end of s, it only contains extra ')'
2) rightStr starting from the right end of s, it only contains extra '('
3) goodStr is a substring of s that has neither extra ')' nor extra '('.
4) This partition operation can be realized by using an explicit stack or implicit stack to record the end of leftStr, the beginning of rightStr, and number of extra ')' in leftStr, and the number of extra '(' in rightStr.
iii. Now we run DFS with backtracking to delete extra ')' in leftStr, and delete extra '(' in rightStr
1) A tricky point is that we must use a variable to indicate whether a partial solution is valid or not. So, we keep an integer p = 0. This is also an implicit stack technique.
2) Every time we append a '(' in the partial solution, p++
3) Every time we append a ')' in the partial solution, p--
4) When p < 0, we know that the partial solution is invalid, we stop the DFS.``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.