[LeetCode] Problem 32 - Longest Valid Parentheses

Posted on | In ,

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

Example

No.1

Input: “(()”

Output: 2

Explanation: The longest valid parentheses substring is “()”

No.2

Input: “)()())”

Output: 4

Explanation: The longest valid parentheses substring is “()()”

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int longestValidParentheses(String s) {
    int result = 0;
    int[] d = new int[s.length()];

    // "()": d[i] = d[i-2] + 2
    // "(...))": d[i] = d[i-1] + d[i - d[i-1] - 2] + 2
    for (int i = 1; i < s.length(); i++) {
        if (s.charAt(i) == ')') {
            if (s.charAt(i - 1) == '(')
                d[i] = (i >= 2 ? d[i - 2] : 0) + 2;
            else if (i - d[i - 1] >= 1 && s.charAt(i - d[i - 1] - 1) == '(')
                d[i] = d[i - 1] + (i - d[i - 1] >= 2 ? d[i - d[i - 1] - 2] : 0) + 2;

            result = Math.max(result, d[i]);
        }
    }

    return result;
}