32. Longest Valid Parentheses

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

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

Solution:

1. Scan forward and count the number of "(" and ")" as left and right.

If left == right, we the parentheses are valid, we update the max length.

If left < right, the parentheses become invalid. We reset left and right to 0.

2. Scan backward and do the same thing but reverse the condition.

The time complexity is O(n) and the space complexity is O(1).



Code:

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