32. Longest Valid Parentheses

Problem

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

Example 1:

Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".

Example 2:

Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".

Example 3:

Input: s = ""
Output: 0

Constraints:

• 0 <= s.length <= 3 * 104
• s[i] is '(', or ')'.

Problem Summary

Given a string containing only '(' and ')', find the length of the longest valid (well-formed and contiguous) parentheses substring.

Solution Ideas

• When parentheses matching is mentioned, the first thing that comes to mind is using a stack. Here we need to calculate the total length of nested parentheses, so the stack should not simply store left parentheses, but should store the indices of left parentheses in the original string, so that the length can be obtained by subtracting indices. If the stack is non-empty, the bottom of the stack always stores the index of the previous unmatched right parenthesis in the string traversed so far. The index of the previous unmatched right parenthesis can be understood as the “partition” between each segment of matched parentheses. For example, in ())((())), the third right parenthesis is the “partition” between the two correct parentheses-matching segments on the left and right. The existence of the “partition” affects the calculation of the longest parentheses length. If there were no “partition”, the two correct parentheses-matching segments before and after it should be “merged” together, and the longest length would be 2 + 6 = 8; however, because the “partition” exists here, the longest length is only 6.
• For the specific algorithm implementation, when encountering each '(', push its index onto the stack. For each encountered ')', first pop the top element of the stack to indicate that the current right parenthesis has been matched. If the stack is empty, it means the current right parenthesis is an unmatched right parenthesis, so push its index into the stack to update the index of the previous unmatched right parenthesis. If the stack is not empty, the index of the current right parenthesis minus the top element of the stack is the length of the longest valid parentheses ending with this right parenthesis. Note that during initialization, the index of the previous unmatched right parenthesis does not exist, so put -1 into the stack to serve as the “partition” at index 0. The time complexity is O(n), and the space complexity is O(n).
• In the stack method, the only element actually used is the index of the previous unmatched right parenthesis at the bottom of the stack. So consider whether this value can be stored in a variable, which can save the O(n) space complexity of the stack. Use two counters, left and right. First, traverse the string from left to right. Whenever '(' is encountered, increase the left counter; whenever ')' is encountered, increase the right counter. Whenever the left counter equals the right counter, calculate the length of the current valid string and record the longest substring found so far. When the right counter is greater than the left counter, it means the parentheses do not match, so reset both the left and right counters to 0. This approach uses a greedy idea, considering the length of the valid parentheses ending at the current character index. Each time the number of right parentheses exceeds the number of left parentheses, the previous characters are discarded and no longer considered, and calculation restarts from the next character.
• However, the above approach misses one case: during traversal, the number of left parentheses is always greater than the number of right parentheses, such as ((); in this case, the longest valid parentheses cannot be found. The solution is to calculate once more in reverse. If calculating from right to left, (() first computes the matched parentheses, and finally only '(' remains, so the longest matched parentheses length can still be calculated. The reverse calculation method is the same as the above left-to-right calculation method: when the left counter is greater than the right counter, reset both the left and right counters to 0; when the left counter equals the right counter, calculate the length of the current valid string and record the longest substring found so far. The time complexity of this method is O(n), and the space complexity is O(1).

Code

package leetcode

// Solution 1 Stack
func longestValidParentheses(s string) int {
	stack, res := []int{}, 0
	stack = append(stack, -1)
	for i := 0; i < len(s); i++ {
		if s[i] == '(' {
			stack = append(stack, i)
		} else {
			stack = stack[:len(stack)-1]
			if len(stack) == 0 {
				stack = append(stack, i)
			} else {
				res = max(res, i-stack[len(stack)-1])
			}
		}
	}
	return res
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

// Solution 2 Two Pointers
func longestValidParentheses1(s string) int {
	left, right, maxLength := 0, 0, 0
	for i := 0; i < len(s); i++ {
		if s[i] == '(' {
			left++
		} else {
			right++
		}
		if left == right {
			maxLength = max(maxLength, 2*right)
		} else if right > left {
			left, right = 0, 0
		}
	}
	left, right = 0, 0
	for i := len(s) - 1; i >= 0; i-- {
		if s[i] == '(' {
			left++
		} else {
			right++
		}
		if left == right {
			maxLength = max(maxLength, 2*left)
		} else if left > right {
			left, right = 0, 0
		}
	}
	return maxLength
}