32. Longest Valid Parentheses Leetcode Dynamic Programming

3 min readApr 5, 2021

Problem Statement :

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

Sample Test Cases:

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

Constraints:

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

Approaches:

We can approach this problem in 2 ways. 1 using a stack and other using dynamic programming.

Stack approach is quite straightforward. We just push the index of the open parentheses and pop when there is closed parentheses.If the stack at the time of popping is empty, we just push the index to stack and update the length.

Below is the code using stack :

class Solution {
    public int longestValidParentheses(String s) {
        int answer = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        for (int i=0; i<s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            }
            else {
                stack.pop();
                if (stack.isEmpty())
                    stack.push(i);
                else
                    answer = Math.max(answer, i - stack.peek());
            }
        }
        return answer;
    }
}

Another approach is by using dynamic programming.

Dynamic Programming Approach

The main concept is we construct a dp array of the length of input string.

Then we traverse through the string and whenever we see an open parentheses ( we just keep the value dp[i] as 0 because for the parentheses to be valid, it must be ended with closed parentheses.

Otherwise if we see a closed parentheses ) , we have 2 options :

> if the character before ie. s.charAt(i-1) is open braces, then we have a valid one, so update dp array

dp[i] = dp[i — 2] + 2 if i — 2>=0 other wise dp[i] = 2.

> if the character before ie. s.charAt(i-dp[i-1]-1)=='(' also i — dp[i-1]-1>=0 , then update the dp array

dp[i] = dp[i-1] + 2 +((i-dp[i-1]-2>=0)?dp[i]-dp[i-dp[i-1]-2]:0)

Update the length everytime we have a valid parentheses.

Code

class Solution {
    public int longestValidParentheses(String s) {
        int length = s.length();
        int [] dp = new int [length];
        int maximum = 0;
        for (int i=1; i<s.length() ; i++) {
            if (s.charAt(i) == '(')
                dp[i] = 0;
            else if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') {
                    dp[i] = i - 2 >= 0 ? dp[i - 2] + 2 : 2;
                }
                else if (i - dp[i - 1] - 1 >= 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                    dp[i] = dp[i - 1] + 2 + ((i - dp[i-1] - 2 >= 0) ? dp[i - dp[i - 1] - 2]: 0);
                }
                maximum = Math.max(dp[i], maximum);
            }
        }
        return maximum;
    }
}