32. Longest Valid Parentheses

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

Example 1:

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

Example 2:

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

Solution

(1) Java

Time Complexity O(n), Space Complexity O(1)

class Solution {
    public int longestValidParentheses(String s) {
        if (s == null || s.length() < 2) {
            return 0;
        }
        int rst = 0;
        int left = 0;
        int right = 0;
        char[] as = s.toCharArray();
        for (int i = 0; i < as.length; i++) {
            char c = as[i];
            if (c == '(') {
                left++;
            } else {
                right++;
            }
            if (left < right) {
                left = 0;
                right = 0;
            } else if (left == right) {
                rst = Math.max(rst, right*2);
            }
        }
        left = 0;
        right = 0;
        for (int i = as.length-1; i >= 0; i--) {
            char c = as[i];
            if (c == '(') {
                left++;
            } else {
                right++;
            }
            if (left > right) {
                left = 0;
                right = 0;
            } else if (left == right) {
                rst = Math.max(rst, right*2);
            }
        }
        return rst;
    }
}

(2) Python

Time Complexity O(n), Space Complexity O(n)

class Solution:
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s:
            return 0
        stack = []
        rst = 0
        for idx, c in enumerate(s):
            if c == '(':
                stack.append(idx)
            else:
                if not stack or s[stack[len(stack)-1]] != '(':
                    stack.append(idx)
                else:
                    stack.pop(len(stack)-1)
                    if not stack:
                        rst = max(rst, idx+1)
                    else:
                        rst = max(rst, idx-stack[len(stack)-1]) 
        return rst

(3) Scala