Longest valid Parentheses

Given a string A containing just the characters ’(‘ and ’)’.

Find the length of the longest valid (well-formed) parentheses substring.

Input Format:

The only argument given is string A.

Output Format:

Return the length of the longest valid (well-formed) parentheses substring.

Constraints:

1 <= length(A) <= 750000

For Example

Input 1:
    A = "(()"
Output 1:
    2
    Explanation 1:
        The longest valid parentheses substring is "()", which has length = 2.

Input 2:
    A = ")()())"
Output 2:
    4
    Explanation 2:
        The longest valid parentheses substring is "()()", which has length = 4.

Solution:

Time: O(n)
Space: O(n)

public class Solution {
    public int longestValidParentheses(String A) {
        // top of stack is the index of the end of previous parenthese
        Deque<Integer> stack = new ArrayDeque<>();
        int maxSize = 0;
        int i = 0;
        stack.push(-1);
        while (i < A.length()) {
            char c = A.charAt(i);
            if (c == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    maxSize = Math.max(maxSize, i - stack.peekFirst());
                }
            }
            i ++;
        }
        return maxSize;
    }
}