# [How to from Error to AC]clean C++ implementation

• my first implementation pass 154 / 229 test cases passed.

Here is the code.

the pair recorded the valid pair count util the current position, but It may contain some cases like this

``````   s = "()(()"  it will return 4 but should return 2. It does contain 2 valid pairs,
but it is not consecutive. so we should reset the pair=0 when meet the cut char !
``````

But it is not easy to identify the cut char before scanning all the chars. so Can anyone think of how to solve This problem.

Original code :

``````class Solution {
public:
int longestValidParentheses(string s) {
int pair=0, left=0, right=0;
int result=0;
for(int i=0; i<s.size(); i++){
if(s[i]=='(')  left++;
else {
if(left>0){
left--;
pair++;
}
/** reset the state **/
else{
pair=0;
left=0;
right=0;
}
}
result=max(result, pair);
}
return 2*result;
}
};``````

• To solve this problem , the top voted answer just record all the invalid position, So we can calculate the range between all the invalid position pair-wise.

Same Idea, and nice way to deal with my problem

Code is like this

``````class Solution {
public:
int longestValidParentheses(string s) {
int n=s.size(), result=0;
stack<int> s_stack;
/** the valid index will be pop out **/
/** the remained index is all in-valid **/
for(int i=0; i<n; i++){
if(s[i]=='(')  s_stack.push(i);
else{
if(!s_stack.empty()){
if(s[s_stack.top()]=='(') s_stack.pop();
else  s_stack.push(i);
}
else
s_stack.push(i);
}
}
if(s_stack.empty()) result=n;
/** all the range based on the remained index in the stack is valid pairs **/
/** scant the stack to get the result **/
else{
int end=n, start=0;
while(!s_stack.empty()){
start=s_stack.top();
s_stack.pop();
result=max(result, end-start-1);
end=start;
}
result=max(result, end);
}
return result;
}
};``````

• So can we use the dynamic programming to solve the problem.

As with most cases, we use the tail-dynamic-programming method to solve this problem.

we use

``````     dp[i]:  record the  max-pairs-end-at-position-i
``````

So, the recursive equation is like this

``````     if s[i]=='('      dp[i]=0
if s[i]==')'      s[i-1]=='('
dp[i]=dp[i-2]+2
s[i-1]==')'  &&  s[i-dp[i-1]-1]=='('
dp[i]=d[i-1]+2+{dp[i-dp[i-1]-2] or 0}
``````

So the final implementation is like this:

``````class Solution {
public:
int longestValidParentheses(string s) {
int len=s.size();
if(len<=1)  return 0;
int result=0;
vector<int> dp(len, 0);
for(int i=1; i<len; i++){
if(s[i]==')'){
if(s[i-1]=='('){
dp[i]=(i-2)>=0 ? dp[i-2]+2 : 2;
result=max(result, dp[i]);
}
else{
if(i-dp[i-1]-1>=0 && s[i-dp[i-1]-1]=='('){
if(i-dp[i-1]-2 >= 0)
dp[i]=dp[i-1]+2+dp[i-dp[i-1]-2];
else
dp[i]=dp[i-1]+2;
result=max(result, dp[i]);
}
}
}
}
return result;
}
};
``````

• The mistake I made is like this

``````for(int i = 0; i < s.size(); i++) {
if(s[i] == '(') {
st.push(i);
}
else {
if(!st.empty() && st.top() == '(')  st.pop();
else  st.push(i);
}
}
``````

• I should use s[st.top()] but not st.top()

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