Longest valid Parentheses

Time: O(n)

Space: O(n)

Intuition

Use a stack to find the length of the longest valid parentheses substring. Push indices; on ')', pop matching '('; if stack empty, push current as new base.

Algorithm

1Push -1 as base index onto stack.
2For '(': push index.
3For ')': pop. If stack empty: push current index as new base. Else: length = i - stack.top(). Update max.

Example Walkthrough

Input: "()(()"

1.i=0 '(' push. i=1 ')' pop, stack=[âˆ’1], len=1âˆ’(âˆ’1)=2. i=2,3 push. i=4 ')' pop, stack=[1], len=4âˆ’1=3.

Output: 4... (recalc: "(()" â†’ len=2 from last two)

Common Pitfalls

•Initialize stack with -1 as sentinel. Also solvable with DP (dp[i] = length ending at i) or two passes.

Longest valid Parentheses.java

Java

// Approach: Stack storing indices. Push -1 as base. On ')' pop; if stack empty push index, else update max span.
// Time: O(n) Space: O(n)
class Solution {
    static int maxLength(String S) {

        int open = 0, close = 0;
        int max = 0;

        // traverse from first
        for (char c : S.toCharArray()) {

            if (c == '(')
                open++;

            else
                close++;

            if (open == close)
                max = Math.max(open + close, max);

            // close is greater than open means , reset
            else if (close > open) {
                open = 0;
                close = 0;
            }
        }

        // traverse from last , if open is greater than means , reset
        open = 0;
        close = 0;

        for (int i = S.length() - 1; i >= 0; i--) {

            if (S.charAt(i) == ')')
                close++;
            else
                open++;

            if (open == close)
                max = Math.max(open + close, max);

            if (open > close) {
                open = 0;
                close = 0;
            }
        }

        return max;
    }
}

Was this solution helpful?