Longest Valid Parentheses

LeetCode Q 32 - Longest Valid Parentheses

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

Example 1:
Input: "(()" ; Output: 2
Explanation: The longest valid parentheses substring is “()”
Example 2:
Input: ")()())" ; Output: 4
Explanation: The longest valid parentheses substring is “()()”

Solution

Solution 1: Stack

The integer stored the index of invalid ‘)’ and last ‘(‘

• whenver we encount a ‘(‘, we also push its index;
• whenever we encounter a ‘)’, we first pop the 1st element from stack, there are two cases:
  • the 1st element is the index of ‘(‘, in which case the stack must not be empty, since we always store the last index of invalid ‘)’ in the stack, then update the maxLen;
  • the 1st element is the index of ‘)’, in which case the stack should be empty, since we only store the last index of invalid ‘)’ in the stack, then update the index of ‘)’ stored in the stack.

public int longestValidParentheses(String s) {
	if (s == null || s.length() < 2)
		return 0;
	
	Stack<Integer> stack = new Stack<>();
	stack.push(-1);
	int maxLen = 0;
	for (int i = 0; i < s.length(); i++) {
		if (s.charAt(i) == '(') {
			stack.push(i);
		} else {
			if (stack.isEmpty())
				stack.push(i);
			else 
				maxLen = Math.max(maxLen, i - stack.peek());
		}
	}

	return maxLen;
}

Solution 2: DP (TODO)