### 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.

- Case 1. Stack is already 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())`

- If

- If
`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