# Longest valid Parentheses

### Longest valid Parentheses

##### Given a string consisting of opening and closing parenthesis, find length of the longest valid parenthesis substring.

Example
Input : ((()
Output : 2

Input: )()())
Output : 4

Input: ()(()))))
Output: 6

Solution:

• We will stack to maintain index of all opening brackets “(“.
• When we encounter “(” we’ll push index of this in stack
• When we encounter “)” then there could be there possible cases
• Case 1. Stack is already empty
• means all valid parenthesis already consumed and after this new start
• Case 2. After pop element from stack, it becomes empty
• Case 3. And even after poping from stack is not empty.
##### Algorithm:
• Create empty stack
• Set `maxLen = 0, last = -1`
• Iterate parenthesis from start to end
• If `currentCharacter is "("` then
• `stack.push(i)`
• Else
• If` stack is empty` then,
• `last = i`
• Else
• `stack.pop`
• If stack is empty then,
• `maxLen = Math.max(maxLen, i - last)`
• Else
• `maxLen = Math.max(maxLen, i - stack.peek())`
• `Return maxLen`

Latest Source Code:
Github: LongestValidParentheses.java

Output:

```Longest Valid Parentheses of ((() :2
Longest Valid Parentheses of )()())()()()() :8
Longest Valid Parentheses of ()(())))) :6
Longest Valid Parentheses of )()()) :4
Longest Valid Parentheses of ()()() :6
Longest Valid Parentheses of  :0
Longest Valid Parentheses of (((( :0
Longest Valid Parentheses of (((() :2
Longest Valid Parentheses of (((())( :4
Longest Valid Parentheses of ()(() :2
Longest Valid Parentheses of ()(()) :6
```
Author: