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;
}


If You Like This Page Then Make Sure To Follow Us on Facebook, G News and Subscribe Our YouTube Channel. We will provide you updates daily.
Shares
facebook sharing button Share
twitter sharing button Tweet
whatsapp sharing button Share
telegram sharing button Share
pinterest sharing button Pin

Leave a Comment