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.