Longest Valid Parentheses Problem Solution

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

Example :

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

Example :

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

Problem Solution In Python

 class Solution:
    def longestValidParentheses(self, s: str) -> int:
        if len(s) <= 1:
            return 0
        stack = []
        maxLen = 0
        stack.append(-1)
        for i in range(len(s)):
            if s[i] == '(':
                stack.append(i)
            elif s[i] == ')':
                if stack[-1] != -1 and s[stack[-1]] == '(':
                    stack.pop()
                    maxLen = max(i - stack[-1],maxLen)
                else:
                    stack.append(i)
                    
        return maxLen

Problem Solution In Java

class Solution {
    public int longestValidParentheses(String s) {
        int ans = 0;
        char l = '(';
        char r = ')';
        int i =0;
        int j;
        int[] save = new int[s.length()];
        
        while (i<s.length()){
            j = i;
            Stack<Integer> st = new Stack<Integer>();
            while(j<s.length()){
                if (s.charAt(j) == l) st.add(j);
                else{
                    if (st.isEmpty()) {
                        i = j+1;
                        break;
                    }
                    save[st.pop()] = 1;
                    save[j] = 1;
                    if (st.isEmpty()) {
                        i = j+1;
                        break;
                    }
                }
                if (j==s.length()-1) i=j+1;
                j++;
            }
        }
        
        i = 0;
        while (i<s.length()){
            if (save[i] != 1) {
                i++;
                continue;
            }
            j = i;
            while (j<s.length() && save[j] == save[i]) {
                j++;
            }
            if ((j-i)>ans) ans = (j-i);
            i = j;
        }
        
        return ans;
}
}

Problem Solution In C++

int longestValidParentheses(string s) {
        stack<int> list;
        list.push(-1);
        int maxa = 0;
        for(int i=0; i< s.length(); ++i){
            if(s[i] == '('){
                list.push(i);
            }
            else{
                list.pop();
                if(list.empty())
                    list.push(i);
                maxa = max(maxa, i - list.top());
                
            }
        }
        return maxa;
        
    }

Problem Solution In C

#define MAXN (32767)

int stck[MAXN],dp[MAXN];

int longestValidParentheses(char* s) {
    int i, ans = 0, top = 0;

    for(i = 0; s[i]; i++)
    {
        dp[i] = 0;
        if(s[i] == '(')
            stck[top++] = i;
        else if(top)
        {
            int tmp = stck[--top];
            dp[i] = i - tmp + 1 + (tmp?dp[tmp-1]:0);
            ans = ans < dp[i]?dp[i]:ans;
        }
    }
    return ans;
}