# Longest valid parentheses

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

```
class Solution:
def longestValidParentheses(self, s: str) -> int:
# stack, used to record index of parenthesis
# initialized to -1 as dummy head for valid parentheses length computation
stack = [-1]
max_length = 0
# linear scan each index and character in input string s
for cur_idx, char in enumerate(s):
if char == '(':
# push when current char is (
stack.append( cur_idx )
else:
# pop when current char is )
stack.pop()
if not stack:
# stack is empty, push current index into stack
stack.append( cur_idx )
else:
# stack is non-empty, update maximal valid parentheses length
max_length = max(max_length, cur_idx - stack[-1])
return max_length
```

It is also possible to solve without a stack

```
class Solution:
def longestValidParentheses(self, s: str) -> int:
max_length = 0
l,r=0,0
# traverse the string from left to right
for i in range(len(s)):
if s[i] == '(':
l+=1
else:
r+=1
if l == r:# valid balanced parantheses substring
max_length=max(max_length, l*2)
elif r>l: # invalid case as ')' is more
l=r=0
l,r=0,0
# traverse the string from right to left
for i in range(len(s)-1,-1,-1):
if s[i] == '(':
l+=1
else:
r+=1
if l == r:# valid balanced parantheses substring
max_length=max(max_length, l*2)
elif l>r: # invalid case as '(' is more
l=r=0
return max_length
```

## Related Problems

Given n pairs of parentheses, write a function to *generate all combinations of well-formed parentheses*.

Given an integer array nums and an integer k, return *the* k *most frequent elements*. You may return the answer in **any order**.

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return *the max sliding window, *ie an array with the max of the k numbers within the window, for each position as the window moves across the input. ex: [6,2,1,4] with k=2 would return [6,2,4]

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

*Merge all the linked-lists into one sorted linked-list and return it.*