# Longest Valid Parentheses

This page explains Java solution to problem `Longest Valid Parentheses` using `Stack` data structure.

## Problem Statement

Given a string containing just the characters `(` and `)`, find the length of the longest valid (well-formed) parentheses substring.

Example 1:

Input: "(()"
Output: 2

Example 2:

Input: ")()())"
Output: 4

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
package com.vc.hard;

import java.util.Stack;

class LongestValidParentheses {
public int longestValidParentheses(String s) {
if(s == null || s.length() == 0) return 0;

Stack<Integer> st = new Stack<>();
st.push(-1);
int maxLength = Integer.MIN_VALUE;
for (int i = 0; i < s.length(); i++) {
if(s.charAt(i) == '(') st.push(i);
else {
st.pop();
if(st.empty()) st.push(i);
else maxLength = Math.max(maxLength, i - st.peek());
}
}
return maxLength == Integer.MIN_VALUE ? 0 : maxLength;
}
}

``````

Let's run one of the sample input `)()())` visually, for better understanding.

## Time Complexity

O(N)Where
N is total number of elements in a input string

O(N)