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!

Join my Email List for more insights, It's Free!😋