 Coder's Cat

2020-02-02

## Challenge Description

https://leetcode.com/problems/longest-valid-parentheses/

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

Example 1:

Example 2:

## Naive Solution

To get the longest valid parentheses, we could enumerate all the substring of input, and check each substring whether is a valid parenthese.

The overall time complexity is $O(N^3)$

Similar but simpler challenge is: LeetCode: Valid Parentheses.

## Approach with stack

Stack could used to check whether a string is a valid parenthese, but how can we get the longest valid parenthese?

When we encounter a ‘(‘, we push the index of current character into the stack, and when we encounter a ‘)’ we pop a index from stack, if stack is empty, we use index - stack.top to get the length of substring.

The time complexity is: $O(N)$, and space complexity is $O(N)$. ## Approach with Dynamic Programming

The key for dynamic programming is constructing a dp array for optimizing time performance.

Suppose dp[i] means the length of the longest valid substring ending at ith index. When loop over the characters in string, there are two scenarios:

1: s[i]=’)’ and s[i-1]=’(‘, string looks like “……()” =>

2: s[i]=’)’ and s[i-1]=’)’, string looks like “((…..))” =>

One example of input is like (()()).

We need to test whether s[i-dp[i-1]-1] is a corresponding ‘(‘, if so we update the dp value: ## Approach without O(N) space

This is a very clever approach, time complexity is still $O(N)$, but space complexity is $O(1)$.

Use left and right to record the number of ‘(‘ and ‘)’, When iterate over string from left to right, update these two count, left+right is the number of current length of valid parentheses. Whenever right > left, set the counts to zero. Do the same thing with scanning from right to left. Preparing for an interview? Check out this!