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

Question

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 1

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<Integer> stack = new Stack<Integer>();
    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 2

We need to store indexes of previously starting brackets in a stack.

We push the first element of stack as a special element as "-1" or any other number which will not occur in the indexes.

Now we traverse through the string, when we encounter "(" braces we push them, else when we encounter ")" we first pop them and

If stack is not empty, we find length of maximum valid substring till that point by taking maximum of result(initialised as zero) and the difference between current index and index at top of the stack.

Else if stack is empty we push the index.

int result=0;
stack<int> s1;
s1.push(-1);
for(int i=0;i<s.size();++i)
{
    if(s[i]=='(')
        s1.push(i);

    else if(s[i]==')')
    {
        s1.pop();

        if(!s1.empty())
            result=max(result,i-s1.top());
        else
            s1.push(i);
    }
}
cout<<result<<endl;

Here 's' is the string and 's1' is the stack.

Answer 3

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 4

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 5

O(n) can be achieved without the conventional use of stacks if you are open to a dynamic approach of finding a valid element and then trying to increase its size by checking the adjoining elements . Firstly we find a single '()' Then we try to find a longer string including this :

The possibilities are:

• ('()') where we check an index before and an index after
• '()'() where we check the next valid unit so that we don't repeat it in the search.

Next we update the start and end indices of the current check in each loop

At the end of the valid string ,check the current counter with the maximum length till now and update if necessary. Link to code in Python on GitHub Click Here.

Answer 6

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<sizeof(arr))
{
    if(a[i] == '(' )
    {
        if(top == ')' ) //top of a stack,
        {
            count = 0;
            push a[i] in stack;
        }
    }
    else
    {
        if(top == '(' )
        {
            count+=2;
            pop from stack;
        }
        else
        {
            push a[i] in stack;
        }
    }
}

print count

Answer 7

The solution below has O(n) time complexity, and O(1) space complexity.

It is very intuitive.

We first traverse the string from left to right, looking for the longest valid substring of parens, using the 'count' method that is normally used to check the validity of parens. While doing this, we also record the maximum length of such a substring, if found.

Then, we do the same while going from right to left.


The algorithm would be as follows:

// Initialize variables

1. count = 0, len = 0, max_len_so_far = 0


// Check for longest valid string of parens while traversing from left to right

2. iterate over input string from left to right:
   - len += 1
   - if next character is '(',
         count += 1
   - if next character is ')',
         count -= 1
   - if (count == 0 and len > max_len_so_far),
         max_len_so_far = len
   - if (count < 0),
         len = 0, count = 0


// Set count and len to zero again, but leave max_len_so_far untouched

3. count = 0, len = 0


// Now do a very similar thing while traversing from right to left
// (Though do observe the switched '(' and ')' in the code below)

4. iterate over input string from right to left:
   - len += 1
   - if next character is ')',
         count += 1
   - if next character is '(',
         count -= 1
   - if (count == 0 and len > max_len_so_far),
         max_len_so_far = len
   - if (count < 0),
         len = 0, count = 0


// max_len_so_far is now our required answer

5. Finally,
   return max_len_so_far

As an example, consider the string

"((())"

Suppose this string is zero-indexed.

We first go left to right.

So, at index 0, count would be 1, then 2 at index 1, 3 at index 2, 2 at index 3, and and 1 at index 4. In this step, max_len wouldn't even change, because count is never 0 again.

Then we go right to left.

At index 4, count is 1, then 2 at index 3, then 1 at index 2, then 0 at index 1.
At this point, len is 4 and max_len_so_far=0, so we set max_len = 4.
Then, at index 0, count is 1.

At this point, we stop and return 4, which is indeed the correct answer.



A proof of correctness is left as an inclusive exercise to the reader.

NOTE: This algorithm could also be very simply tweaked to return the longest valid substring of parentheses itself, rather than just its length.

Answer 8

public static void main(String[] args) {
    String s="))((())";
    String finalString="";
    for(int i=0;i<s.length();i++){

         if (s.charAt(i) == '('&& s.charAt(i+1) == ')') {
         String ss= s.substring(i, i+2);
         finalString=finalString+ss;
        // System.out.println(ss);
         }

    }
    System.out.println(finalString.length());
}

Answer 9

Using Dynamic Programing to Store and re-use already computed results

def longest_valid_paranthesis(str):
    l = len(str)
    dp = [0]*len(str)
    for i in range(l):
        if str[i] == '(':
            dp[i] = 0
        elif str[i-1] == '(':
            dp[i] = dp[i-2] + 2
        elif str[i - dp[i-1] - 1] == '(':
            dp[i] = dp[i-1] + 2 + dp[i - (dp[i-1] + 2)]

Answer 10

    static int LongestvalidParentheses()
    {
        int cnt = 0;
        string str = "()()))()";
        char f = '(';
        char s = ')';
        var chararr = str.ToCharArray();
        for (int i = 0; i < str.Length - 1; i++)
        {
            if (chararr[i] == f)
            {
                if (chararr[i + 1] == s)
                {
                    cnt++;
                }
            }
        }
        return cnt;
    }