Longest Valid Parentheses

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

Example 1:

Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".

Example 2:

Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".

Example 3:

Input: s = ""
Output: 0

Constraints:

  • 0 <= s.length <= 3 * 104
  • s[i] is '(', or ')'.

Solution

Java Program

class Solution {
    public int longestValidParentheses(String s) {
        
        Stack stack = new Stack<>();
        int left = -1;
        int maxLength = 0;
        for(int index = 0; index < s.length(); index++)
        {
            char c = s.charAt(index);
            if(c == '(')
            {
                stack.push(index);
            }
            else
            {
                if(stack.isEmpty())
                    left = index;
                else
                {
                    stack.pop();
                    if(stack.isEmpty())
                    {
                        int lengthUsingLeft = index - left;
                        maxLength = Math.max(maxLength, lengthUsingLeft);
                    }
                    else
                    {
                        int lengthUsingIndex = index - stack.peek();
                        maxLength = Math.max(maxLength,lengthUsingIndex);
                    }
                }
            }
        }
        return maxLength;
    }
    
}

Code walk through

s = "((()))"
i = "012345"

left = -1;
max = 0;

At i = 0,
stack = [0];

At i = 1,
stack = [0,1];

At i = 2,
stack = [0,1,2];

At i = 3,
stack = [0,1];
len = 3 - 1 => 2;
max = 2;

At i = 4, 
stack = [0]
len = 4 - 0 => 4;
max = 4;

At i = 5,
stack = [];
len = 5 - (-1) => 6;
max = 6;


s = ")()(())"
i = "0123456"
left = -1;

At i = 0,
left = i;
left = 0;


At i = 1;
stack = [1]


At i = 2,
stack = [];
length = 2

At i = 3,
stack = [3]

At i = 4,
stack = [3,4]

At i = 5,
stack = [3]

length = 2


At i = 6;
stack = [];

length = i - left;
length = 6;


Time Complexity: O(N)

Space Complexity: O(N)

Leave a Comment

Your email address will not be published. Required fields are marked *