[LeetCode] 32. Longest Valid Parentheses

Posted on | In

Problem

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

Example 1:

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

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

Explanation

  1. We can loop through the string character by character. If the character is (, we push its index to the stack. Else if the character is ), we pop an element of the stack then the length will be the current index subtract the top element of the stack. If after we pop an element of the stack, the stack become empty, then the length will be the current index subtract the leftmost element. If Before we pop an element of the stack, the stack is empty, then we set the leftmost element to the current index.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
           Example: s = ( ( ) ( ) ) ( ) )
       char      idx      leftmost      stack      pop      max
                            -1            E                  0
       (         0          -1            0                  0
       (         1          -1            01                 0
       )         2          -1            0         1       2-0
       (         3          -1            03                 2
       )         4          -1            0         3       4-0
       )         5          -1            E         0       5-(-1)
       (         6          -1            6                  6
       )         7          -1            E         6       7-(-1)
       )         8           8            E                  8

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int longestValidParentheses(String s) {
        if (s == null || s.length() < 2) return 0;
        Stack<Integer> st = new Stack<>();
        int res = 0;
        int leftMost = -1;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                st.push(i);
            } else {
                if (st.isEmpty()) {
                    leftMost = i;
                } else {
                    st.pop();
                    if (st.isEmpty()) {
                        res = Math.max(res, i-leftMost);
                    } else {
                        res = Math.max(res, i-st.peek());
                    }
                }
            }
        }

        return res;
    }
}