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\na valid string of parentheses or not. In order to check the validity, we use the Stack\'s Method.

Every time we\nencounter a $$\\text{\xe2\x80\x98(\xe2\x80\x99}$$ , we push it onto the stack. For every $$\\text{\xe2\x80\x98)\xe2\x80\x99}$$ encountered, we pop a $$\\text{\xe2\x80\x98(\xe2\x80\x99}$$ from the stack. If $$\\text{\xe2\x80\x98(\xe2\x80\x99}$$ isn\'t\n 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\n process for every possible substring and we keep on\n storing the length of the longest valid string found so far.

Example:\n"((())"\n\n(( --> invalid\n(( --> invalid\n() --> valid, length=2\n)) --> invalid\n((()--> invalid\n(())--> valid, length=4\nmaxlength=4\n

Complexity Analysis

\n
• \n

  Time complexity : $$O(n^3)$$ . Generating every possible substring from a string of length $$n$$ requires $$O(n^2)$$ . Checking validity of a string of length $$n$$ requires $$O(n)$$ .

  \n
\n
• \n

  Space complexity : $$O(n)$$ . A stack of depth $$n$$ will be required for the longest substring.

  \n
\n

Approach #2 Using Dynamic Programming [Accepted]

Algorithm

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

To fill $$\\text{dp}$$ array we will check every two consecutive characters of the string and if

\n
1. \n

   \n $$\\text{s}[i] = \\text{\xe2\x80\x98)\xe2\x80\x99}$$ and $$\\text{s}[i - 1] = \\text{\xe2\x80\x98(\xe2\x80\x99}$$ , i.e. string looks like $$``.......()" \\Rightarrow$$ \n

   \n

   \n $$\n\\text{dp}[i]=\\text{dp}[i-2]+2\n$$ \n

   \n

   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.

   \n
\n
2. \n

   \n $$\\text{s}[i] = \\text{\xe2\x80\x98)\xe2\x80\x99}$$ and $$\\text{s}[i - 1] = \\text{\xe2\x80\x98)\xe2\x80\x99}$$ , i.e. string looks like $$``.......))" \\Rightarrow$$ \n

   \n

   if $$\\text{s}[i - \\text{dp}[i - 1] - 1] = \\text{\xe2\x80\x98(\xe2\x80\x99}$$ then

   \n

   \n $$\n\\text{dp}[i]=\\text{dp}[i-1]+\\text{dp}[i-\\text{dp}[i-1]-2]+2\n$$ \n

   \n
\n

The reason behind this is that if the 2nd last $$\\text{\xe2\x80\x98)\xe2\x80\x99}$$ was a part of a valid substring (say $$sub_s$$ ), for the last $$\\text{\xe2\x80\x98)\xe2\x80\x99}$$ to be a part of a larger substring, there must be a corresponding starting $$\\text{\xe2\x80\x98(\xe2\x80\x99}$$ which lies before the valid substring of which the 2nd last $$\\text{\xe2\x80\x98)\xe2\x80\x99}$$ is a part (i.e. before $$sub_s$$ ). Thus, if the character before $$sub_s$$ happens to be $$\\text{\xe2\x80\x98(\xe2\x80\x99}$$ , we update the $$\\text{dp}[i]$$ as an addition of $$2$$ in the length of $$sub_s$$ which is $$\\text{dp}[i-1]$$ . To this, we also add the length of the valid substring just before the term "(,sub_s,)" , i.e. $$\\text{dp}[i-\\text{dp}[i-1]-2]$$ .

For better understanding of this method, see this example:

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

Complexity Analysis

\n
• \n

  Time complexity : $$O(n)$$ . Single traversal of string to fill dp array is done.

  \n
\n
• \n

  Space complexity : $$O(n)$$ . dp array of size $$n$$ is used.

  \n
\n

Approach #3 Using Stack [Accepted]

Algorithm

Instead of finding every possible string and checking its validity, we can make use of stack while scanning\nthe 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 $$-1$$ onto the stack.

For every $$\\text{\xe2\x80\x98(\xe2\x80\x99}$$ encountered, we push its index onto the stack.

For every $$\\text{\xe2\x80\x98)\xe2\x80\x99}$$ 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

\n
• \n

  Time complexity : $$O(n)$$ . $$n$$ is the length of the given string..

  \n
\n
• \n

  Space complexity : $$O(n)$$ . The size of stack can go up to $$n$$ .

  \n
\n

Approach #4 Without extra space [Accepted]

Algorithm

In this approach, we make use of two counters $$left$$ and $$right$$ . First, we start traversing the string from the left towards the right and for every $$\\text{\xe2\x80\x98(\xe2\x80\x99}$$ encountered, we increment the $$left$$ counter and for every $$\\text{\xe2\x80\x98)\xe2\x80\x99}$$ encountered, we increment the $$right$$ counter. Whenever $$left$$ becomes equal to $$right$$ , we calculate the length of the current valid string and keep track of maximum length substring found so far. If $$right$$ becomes greater than $$left$$ we reset $$left$$ and $$right$$ to $$0$$ .

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

\n
• \n

  Time complexity : $$O(n)$$ . Two traversals of the string.

  \n
\n
• \n

  Space complexity : $$O(1)$$ . Only two extra variables $$left$$ and $$right$$ are needed.

  \n
\n

Analysis written by: @vinod23