Find the length of the longest valid parenthesis sequence in a string, in O(n) time

Find the length of the longest valid parenthesis sequence in a string, in O(n) time

My friend ran into a question in an interview and he was told that there is an O(n) solution. However, neither of us can think it up. Here is the question:

There is a string which contains just ( and ), find the length of the longest valid parentheses substring, which should be well formed.

For example ")()())", the longest valid parentheses is ()() and the length is 4.

I figured it out with dynamic programming, but it is not O(n). Any ideas?

public int getLongestLen(String s) {      if (s == null || s.length() == 0)          return 0;        int len = s.length(), maxLen = 0;      boolean[][] isValid = new boolean[len][len];      for (int l = 2; l < len; l *= 2)          for (int start = 0; start <= len - l; start++) {              if ((s.charAt(start) == '(' && s.charAt(start + l - 1) == ')') &&                   (l == 2 || isValid[start+1][start+l-2])) {                      isValid[start][start+l-1] = true;                      maxLen = Math.max(maxLen, l);                  }          }        return maxLen;  }  

Answer by David for Find the length of the longest valid parenthesis sequence in a string, in O(n) time

I did this question before, and it is not easy to come up with O(n) solution under pressure. Here is it, which is solved with stack.

   private int getLongestLenByStack(String s) {      //use last to store the last matched index      int len = s.length(), maxLen = 0, last = -1;      if (len == 0 || len == 1)          return 0;        //use this stack to store the index of '('      Stack stack = new Stack();      for (int i = 0; i < len; i++) {          if (s.charAt(i) == '(')               stack.push(i);          else {              //if stack is empty, it means that we already found a complete valid combo              //update the last index.              if (stack.isEmpty()) {                  last = i;                      } else {                  stack.pop();                  //found a complete valid combo and calculate max length                  if (stack.isEmpty())                       maxLen = Math.max(maxLen, i - last);                  else                  //calculate current max length                      maxLen = Math.max(maxLen, i - stack.peek());              }          }      }        return maxLen;  }  

Answer by nbrooks for Find the length of the longest valid parenthesis sequence in a string, in O(n) time

You can increment/decrement an int variable for each open-parenthesis/close-parenthesis respectively. Keep track of the number of such valid operations (where the variable doesn't go below 0) as the current length, and keep track of the longest-such as the max.

public int getLongestLen(String s) {      if (s == null || s.length() == 0) {          return 0;             }        int stack = 0;      int counter = 0;      int max = 0;        for (Character c: s.toCharArray()) {          if (c == '(') {              stack++;          }          if (c == ')') {              stack--;          }          if (stack >= 0) {              counter++;          }          if (stack < 0) {              counter = 0;              stack = 0;          }          if (counter > max && stack == 0) {              max = counter;          }      }        return max;  }  

Answer by Haris for Find the length of the longest valid parenthesis sequence in a string, in O(n) time

just came up with the solution, do comment if there is anything wrong

count = 0 //stores the number of longest valid paranthesis  empty stack s  arr[]; //contains the string which has the input, something like ())(()(  while(i

print count

Answer by harishvc for Find the length of the longest valid parenthesis sequence in a string, in O(n) time

ALGORITHM: Entire code on GitHub
1. Add to stack
1.1 initialize with -1,handle )) without ((
2. When you see ) pop from stack
2.a if stack size == 0 (no match), push current index values
2.b if stack size > 0 (match), get max length by subtracting index of value at top from current index (totally wicked!)

def longestMatchingParenthesis(a):      pstack = []        #index position of left parenthesis      pstack.append(-1)  #default value; handles ) without ( and when match adds up to 2!      stack_size = 1       result = 0      for i in range(0,len(a)):              if a[i] == '(':                      pstack.append(i) #Append current index                      stack_size += 1              else:    # handle )                      pstack.pop()                      stack_size -= 1                      #determine length of longest match!                      if stack_size > 0:                              #difference of current index - index at top of the stack (yet to be matched)                              result = max(result, i - pstack[-1])                      else:                              #stack size == 0, append current index                              pstack.append(i)                              stack_size += 1       return result    a = ["()()()", "", "((((", "(((()", "(((())(", "()(()" ,"()(())"]  for x in a:      print("%s = %s" % (x,longestMatchingParenthesis(x)))    #output  ()()() = 6  = 0  (((( = 0  (((() = 2  (((())( = 4  ()(() = 2  ()(()) = 6  

Answer by Ashish for Find the length of the longest valid parenthesis sequence in a string, in O(n) time

Please find the simplest working solution.

#include "stdafx.h"  #include   #include   #include   #include   int findMaxLen(string str)  {  int n = str.length();    // Create a stack.  stack stk;      // Initialize result  int result = 0;    // Traverse all characters of given string  for (int i = 0; i

Fatal error: Call to a member function getElementsByTagName() on a non-object in D:\XAMPP INSTALLASTION\xampp\htdocs\endunpratama9i\www-stackoverflow-info-proses.php on line 72