import java.util.*;

class Solution {
    public int longestValidParentheses(String s) {
        char[] chs = s.toCharArray();
        Stack<Integer> stack = new Stack<>();
        int max = 0, pre = -1;
        for (int i = 0; i < chs.length; i++) {
            char ch = chs[i];
            if (ch == '(') {
                stack.push(i);
                continue;
            } else if (stack.isEmpty()) {
                pre = i;
                continue;
            }
            stack.pop();
            if (stack.isEmpty()) max = Math.max(max, i - pre);
            else max = Math.max(max, i - stack.peek());
        }
        return max;
    }
}