O(n) solution checkout


#1

int Solution::longestValidParentheses(string A) {
int n=A.length();
stack stac;
stac.push(-1);
int maxi=0;
for(int i=0;i<n;i++){
int top = stac.top();
if(A[top]==’(’&&A[i]==’)’){
stac.pop();
int newtop = stac.top();
maxi = max(maxi,i-newtop);
}
else{
stac.push(i);
}
}
return maxi;
}


#2

your solution needs some modification, it’s giving a correct answer here but it’s wrong, it will give runtime error on any other place. I pointed your mistake as when we will check for i=0 then at that time in your stack -1 is there and you are using it as the index, which is not possible.
Hope you got the mistake.