package leetcode;

import java.util.Stack;

/**
 * https://leetcode.com/problems/longest-valid-parentheses/
 */
public class Problem32 {
    public int longestValidParentheses(String s) {
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                stack.add(i);
            } else {
                if (!stack.isEmpty()) {
                    int idx = stack.peek();
                    if (s.charAt(idx) == '(') {
                        stack.pop();
                    } else {
                        stack.push(i);
                    }
                } else {
                    stack.push(i);
                }
            }
        }
        if (stack.isEmpty()) {
            return s.length();
        }
        int max = 0;
        int a = s.length();
        while (!stack.isEmpty()) {
            int b = stack.pop();
            max = Math.max(max, a - b - 1);
            a = b;
        }
        max = Math.max(max, a);
        return max;
    }

    public static void main(String[] args) {
        Problem32 prob = new Problem32();
        System.out.println(prob.longestValidParentheses("(()")); // 2
        System.out.println(prob.longestValidParentheses(")()())")); // 4
        System.out.println(prob.longestValidParentheses("(")); // 0
        System.out.println(prob.longestValidParentheses("()(())")); // 6
        System.out.println(prob.longestValidParentheses("((())))")); // 6
        System.out.println(prob.longestValidParentheses("()(()(")); // 2
        System.out.println(prob.longestValidParentheses(")()()(")); // 4
        System.out.println(prob.longestValidParentheses("()((())")); // 4
        System.out.println(prob.longestValidParentheses("()(())")); // 6
        System.out.println(prob.longestValidParentheses("()()(()(((()))()))()))))()(())))()(()())()()()))())))())())))(()()()))))()((()(())(())))((()())(()()()((((()(())))))((()()((())(())(()(())))))()()())(())(()())((()())()(((())))()(()()))")); // 96
        System.out.println(prob.longestValidParentheses(")((()()((((()((((())(())(((()((((())(()((())())())(()))))))))))))(())(()())((())))))(((((()))())))(()()))(())))((()()(()()()()())))()(())((())()(())(((()())((())))(())))()())))))())()())())(((()")); // 108
    }
}

@@ -1071,1268 +1071,7 @@
    %7D
-%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem32 prob = new Problem32();%0A        System.out.println(prob.longestValidParentheses(%22(()%22)); // 2%0A        System.out.println(prob.longestValidParentheses(%22)()())%22)); // 4%0A        System.out.println(prob.longestValidParentheses(%22(%22)); // 0%0A        System.out.println(prob.longestValidParentheses(%22()(())%22)); // 6%0A        System.out.println(prob.longestValidParentheses(%22((())))%22)); // 6%0A        System.out.println(prob.longestValidParentheses(%22()(()(%22)); // 2%0A        System.out.println(prob.longestValidParentheses(%22)()()(%22)); // 4%0A        System.out.println(prob.longestValidParentheses(%22()((())%22)); // 4%0A        System.out.println(prob.longestValidParentheses(%22()(())%22)); // 6%0A        System.out.println(prob.longestValidParentheses(%22()()(()(((()))()))()))))()(())))()(()())()()()))())))())())))(()()()))))()((()(())(())))((()())(()()()((((()(())))))((()()((())(())(()(())))))()()())(())(()())((()())()(((())))()(()()))%22)); // 96%0A        System.out.println(prob.longestValidParentheses(%22)((()()((((()((((())(())(((()((((())(()((())())())(()))))))))))))(())(()())((())))))(((((()))())))(()()))(())))((()()(()()()()())))()(())((())()(())(((()())((())))(())))()())))))())()())())(((()%22)); // 108%0A    %7D
 %0A%7D%0A

Solve problem 32