32. Longest Valid Parentheses


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

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.


Summary

We need to determine the length of the largest valid substring of parentheses from a given string.

Solution

Approach #1 Brute Force [Time Limit Exceeded]

Algorithm

In this approach, we consider every possible non-empty even length substring from the given string and check whether it's a valid string of parentheses or not. In order to check the validity, we use the Stack's Method.

Every time we encounter a , we push it onto the stack. For every encountered, we pop a from the stack. If isn't available on the stack for popping at anytime or if stack contains some elements after processing complete substring, the substring of parentheses is invalid. In this way, we repeat the process for every possible substring and we keep on storing the length of the longest valid string found so far.

Example:
"((())"

(( --> invalid
(( --> invalid
() --> valid, length=2
)) --> invalid
((()--> invalid
(())--> valid, length=4
maxlength=4

Complexity Analysis

  • Time complexity : . Generating every possible substring from a string of length requires . Checking validity of a string of length requires .

  • Space complexity : . A stack of depth will be required for the longest substring.

Approach #2 Using Dynamic Programming [Accepted]

Algorithm

This problem can be solved by using Dynamic Programming. We make use of a array where th element of represents the length of the longest valid substring ending at th index. We initialize the complete array with 0's. Now, it's obvious that the valid substrings must end with . This further leads to the conclusion that the substrings ending with will always contain '0' at their corresponding indices. Thus, we update the array only when is encountered.

To fill array we will check every two consecutive characters of the string and if

  1. and , i.e. string looks like

    We do so because the ending "()" portion is a valid substring anyhow and leads to an increment of 2 in the length of the just previous valid substring's length.

  2. and , i.e. string looks like

    if then

The reason behind this is that if the 2nd last was a part of a valid substring (say ), for the last to be a part of a larger substring, there must be a corresponding starting which lies before the valid substring of which the 2nd last is a part (i.e. before ). Thus, if the character before happens to be , we update the as an addition of in the length of which is . To this, we also add the length of the valid substring just before the term "(,sub_s,)" , i.e. .

For better understanding of this method, see this example:

!?!../Documents/32_Longest_Valid2.json:1000,563!?!

Complexity Analysis

  • Time complexity : . Single traversal of string to fill dp array is done.

  • Space complexity : . dp array of size is used.

Approach #3 Using Stack [Accepted]

Algorithm

Instead of finding every possible string and checking its validity, we can make use of stack while scanning the given string to check if the string scanned so far is valid, and also the length of the longest valid string. In order to do so, we start by pushing onto the stack.

For every encountered, we push its index onto the stack.

For every encountered, we pop the topmost element and subtract the current element's index from the top element of the stack, which gives the length of the currently encountered valid string of parentheses. If while popping the element, the stack becomes empty, we push the current element's index onto the stack. In this way, we keep on calculating the lengths of the valid substrings, and return the length of the longest valid string at the end.

See this example for better understanding.

!?!../Documents/32_Longest_Valid_stack_new.json:1000,563!?!

Complexity Analysis

  • Time complexity : . is the length of the given string..

  • Space complexity : . The size of stack can go up to .

Approach #4 Without extra space [Accepted]

Algorithm

In this approach, we make use of two counters and . First, we start traversing the string from the left towards the right and for every encountered, we increment the counter and for every encountered, we increment the counter. Whenever becomes equal to , we calculate the length of the current valid string and keep track of maximum length substring found so far. If becomes greater than we reset and to .

Next, we start traversing the string from right to left and similar procedure is applied.

Example of this approach:

!?!../Documents/32_Longest_Validlr.json:1000,563!?!

Complexity Analysis

  • Time complexity : . Two traversals of the string.

  • Space complexity : . Only two extra variables and are needed.

Analysis written by: @vinod23

Submit Solution