Longest Valid Parenthesis

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.

First look at the problem we first let identify whether a string of parenthesis are valid. For example,

()) invalid
(() invalid
)(()) invalid
(())() valid
(()()) valid
())(() invalid
))((())() invalid

How, can we check this in fastest possible time? We can use a stack as keep pushing ope parenthesis and keep popping when we see an ending parenthesis. At the end if the stack is empty it means that all the open parenthesis have a matching end parenthesis and hence they are valid.

def isValid(str) :
  Stack stack;

  foreach(character c in str)
      if (c == '(') then
           stack.push(c);
      else
           if(stack.isEmpty)
              return false;
           stack.pop();
      end
  end

  return stack.isEmpty()
end

This is O(n) time and O(n) space solution. Can we do better with space? We can, instead of stack we can keep track of a count variable. We can increase the variable each time we see ‘(‘ and decrease each time we see ‘)’. If count ever goes negative that means we have a ending parenthesis with unmatched opening parenthesis. So, it is invalid. At the end if count is zero then the parentheses are valid otherwise invalid. Below is O(1) pseudocode –

def isValid(str) :
  int count;

  foreach(character c in str)
      if (c == '(') then
           count++;
      else
           if(count == 0)
              return false;
           count--;
      end
  end

  return (count == 0)
end

Longest Valid Parenthesis
How do we compute the longest valid parenthesis substring in a string? Note that, for string (((() the longest valid parenthesis is () the last matching pair of parenthesis. Also, for string ))))() longest valid is the pair that matches. However, For string (()((()) the longest valid is (()). So, couple of observations –

1. We match an ending parenthesis with the last seen opening parenthesis. 
   So, we can use a stack to keep track of position of last '('.

2. Any substring that ends with a ')' that has no matching start '(', then it can't be part of any valid substring. 
   So, we try next substring by starting from next position of this ')'.  

Now, we can compute valid substring positions. But how to compute maximum length? If we think more carefully then we would see that this problem is similar to maximum sum substring problem we discussed here. we can solve this problem by Kadane’s algorithm where instead of maximizing sum of contagious array we are trying to maximize length of contagious valid parenthesis. Kadane’s algorithm works by finding a local maxima so far in the scan from left to right and update the global maxima and start of global maxima accordingly.

The algorithm is as follows –

• Scan each character left to right
• Current character is ‘(‘ : it is part of current local maxima. Push the position into a stack to compute length of local this maxima later when we see a matching end parenthesis.
• Current character is ‘)’ ; we have 2 cases –
  • Stack is empty : it means we don’t have a matching start. We can’t include this ‘)’ in the current substring effectively starting a new substring from next position. So, we save the start position of this new substring. For example, consider the case for ())(()).
  • Stack is not empty : it means we have a matching start ‘(‘ and hence end of a local maxima substring. So, pop out the ‘(‘ and update the local maxima with the length of the substring (current_end_index – poped_start_index+1). After popping the starting ‘(‘ we have one special case though –
    • The stack is empty : it means that this local maxima substring can be a part of a longer substring. For example consider the case for ()()(). So, we need to update the maxima with the longer maxima starting from our saved start position we computed earlier i.e update maxima using length, len = i-start.

Below is the implementation of the above algorithm which takes O(n) time and O(n) space.

public static int longestValidParenthesis(String str){
	int maxLen = 0;
	int start = 0;
	Stack<Integer> stack = new Stack<Integer>();
	
	for(int i = 0; i<str.length(); i++){
		if(str.charAt(i) == '('){
			stack.push(i);
		}
		else{
			//no matching left - update start to next position
			if(stack.isEmpty()){
				start = i+1;
			}
			else{
				int startIndex = stack.pop();
				//update maxima
				maxLen = Math.max(maxLen, i-startIndex+1);
				//after poping start if there is no start left on the stack indicating 
				//that this pair of parenthesis may be a part of longer substring
				//for example, consider the case for ()()()
				if(stack.isEmpty()){
					maxLen = Math.max(maxLen, i-start+1);
				}
			}
		}
	}
	
	return maxLen;
}

Better solution – O(1) Constant Space Solution

Can we do better? Instead of using stack can we use the counting method we described earlier? Let’s give a try. Note that, a string becomes invalid for the first unmatched ‘)’ or the last unmatched ‘(‘. Can we us this signal to implement a solution (think)?

We can actually find maximum length valid substring by scanning left to right and keep counting valid pairs (increment length by 2 for each match) until we see a unmatched ‘)’. A valid pair would contribute 0 to overall count but would contribute 2 to length. So, whenever we see count == 0 this will indicate end of a local maxima. So, update global max at that point only. This will compute max substring that ends with unmatched ‘)’. This is not global max because there can be max substring with invalid ‘(‘. For example, ()())(((()). In order to find maximum substring that can have invalid ‘(‘ we can scan from right to left and do the above same counting procedure. Final global maxima would be the maximum of the two global maxima computed from both end.

Below is the O(n) time and O(1) space solution of the above idea.

public static int longestValidParenthesis(String str, int dir){
	int start = 0;
	int end = str.length()-1;
	int openChar = '(';
	int count = 0;
	int maxLen = 0;
	int curLen = 0;
	if(dir == -1){
		start = end;
		end = 0;
		openChar = ')';
	}
	
	for(int i = start; i!=end; i+=dir){
		if(str.charAt(i) == openChar){
			count++;
		}
		else{
			//no matching left
			if(count <= 0){
				//restart
				curLen = 0;
			}
			else{
				//a local match
				count--;
				curLen += 2;
				
				if(count == 0){
					maxLen = Math.max(maxLen, curLen);
				}
			}
		}
	}
	
	return maxLen;
}

public static int longestValidParenthesis2(String str){
	return Math.max(longestValidParenthesis(str, 1), longestValidParenthesis(str, -1));
}