# Linear time constant space solution for Longest Valid Parentheses

• This problem has only two cases, insufficient ( or insufficient ). Hence, I get a linear time constant space solution.

``````class Solution {
public:
// my unique solution
// take care of the case "()(()"
// can also maitain the position of the left "("
int longestValidParentheses(string s) {
int result1 = 0, result2 = 0;
int r = 0;
int mystack = 0;
for(int i=0; i<s.size(); i++){
if(s[i]=='(')
mystack++;
else{
if(mystack==0)  // reset and restart
r = 0;
else{ // a pair of well-formed parentheses is found
mystack--;
r += 2;
if(mystack==0&&r>result1)
result1 = r;
}
}
}
r = 0;
mystack = 0;
for(int i=s.size()-1; i>=0; i--){
if(s[i]==')') // the key
mystack++;
else{
if(mystack==0)  // reset and restart
r = 0;
else{ // a pair of well-formed parentheses is found
mystack--;
r += 2;
if(mystack==0&&r>result2)
result2 = r;
}
}
}
return result1>result2?result1:result2;
}
};``````

• s[i]? s is a string, not an array, u mean s.toCharArray()?

• s is a string, s[i] is the (i+1)-th character in the string. The data type of string can be used in a manner that is similar to an array.

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