Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

&nbsp;
Example 1:

Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".


Example 2:

Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".


Example 3:

Input: s = ""
Output: 0


&nbsp;
Constraints:


	0 &lt;= s.length &lt;= 3 * 104
	s[i] is '(', or ')'.


class Solution:
    def longestValidParentheses(self, s: str) -> int:

        maxi = 0
        stack = [-1]

        for i in range(len(s)) :
            if s[i] == "(" : stack.append(i)
            else :
                stack.pop()
                if len(stack) == 0 : stack.append(i)
                else : maxi = max(maxi, i - stack[-1])

        return maxi
class Solution {
    public int longestValidParentheses(String s) {
        int i=0;
        int len=0;
        while(i<s.length()){
            int j=i;
            int open=0;
            int closed=0;
            while(j<s.length()){
                char ch = s.charAt(j);
                if(ch=='(') open++;
                if(ch==')') closed++;
                if(closed>open) break;
                if(open==closed) len=Math.max(len,j-i+1);

                j++;
            }
            i++;
        }
        return len;
    }
}
class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.length(), i = 0, ans = 0, k = 0;
        for(int j = 0; j < n; j++) {
            if(s[j] == '(') k++;
            else if(s[j] == ')') {
                k--;
                if(k == 0)
                    ans = max(ans, j - i + 1);
            }
            if(k < 0) {
                k = 0;
                i = j + 1;
            }
        }
        k = 0, i = n - 1;
        for(int j = n - 1; j >= 0; j--) {
            if(s[j] == ')') {
                k++;
            }
            else if(s[j] == '(') {
                k--;
                if(k == 0)
                    ans = max(ans, i - j + 1);
            }
            if(k < 0) {
                k = 0;
                i = j - 1;
            }
        }
        return ans;
    }
};
var longestValidParentheses = function(s) {
    let indexStack=[-1]
    let characterStack=[];
    let maxLength=0;
    for(let i=0;i<s.length;i++){
        if(s[i]=='('){
            indexStack.push(i);
            characterStack.push(s[i]);
        }else{
            if(characterStack[characterStack.length-1]=='('){
                indexStack.pop();
                characterStack.pop();
                if(maxLength<i-indexStack[indexStack.length-1]){
                    maxLength=i-indexStack[indexStack.length-1];
                }
            }else{
                indexStack.push(i);
            }
        }
    }
    return maxLength;
};
Longest Valid Parentheses