# 32. Longest Valid Parentheses

{% hint style="info" %}
Stack, java stack.empty() return bool
{% endhint %}

```java
class Solution {
    public int longestValidParentheses(String s) {
        Stack<Integer> memo = new Stack<Integer>();
        int result = 0;
        for(int i = 0; i<s.length(); i++){
            
            // if current char is '(', push the index
            // if current char is ')' and the char on top of the stack is ')'
            // then it means a valid pair
            // if current char is ')',but the char on top of the stack is ')'
            // then push the index to the stack
            if(s.charAt(i)==')' && !memo.empty() && s.charAt(memo.peek()) =='('){
                memo.pop();
            }else{
                memo.push(i);
            }
        }
        
        // what's left in the stack are the indices of characters that cannot be paired 
        // the gaps (including the the gap between end of S to the first index on the stack, and the gap between the last index of the stack and the end of S) represent the length of the valid pairs.
        int currIndex = s.length();
        while(!memo.empty()){
            result = Math.max(result, currIndex - memo.peek()-1);
            currIndex = memo.pop();
        }
        result = Math.max(result, currIndex);
        return result;
    }
}
```
