# Question

Formatted question description: https://leetcode.ca/all/32.html

Given a string containing just the characters '(' and ')', return 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 ')'.

# Algorithm

To solve with the help of the stack, you need to define a start variable to record the starting position of the valid bracket string.

Traverse the string,

• if it encounters a left bracket, push the current index onto the stack,
• if it encounters a right bracket,
• if the current stack is empty, the next index position is recorded to be start,
• if the stack is not empty, the top element of the stack is taken out, at this time,
• if the stack is empty, update the result and the larger value of i-start + 1,
• otherwise update the result and i-the greater value in st.top()

# Code

• 
public class Longest_Valid_Parentheses {

class Solution_noExtraSpace {
public int longestValidParentheses(String s) {
int res = 0, left = 0, right = 0, n = s.length();

// from left to right, '(()' => will never hit left==right
for (int i = 0; i < n; ++i) {
if (s.charAt(i) == '(') ++left;
else ++right;

if (left == right) res = Math.max(res, 2 * right);
else if (right > left) left = right = 0;
}

// from right to left, '())' => will never hit left==right
left = right = 0;
for (int i = n - 1; i >= 0; --i) {
if (s.charAt(i) == '(') ++left;
else ++right;

if (left == right) res = Math.max(res, 2 * left);
else if (left > right) left = right = 0;
}
return res;

}
}

class Solution_stack {
public int longestValidParentheses(String s) {
Stack<Integer> sk = new Stack<>();
int start = 0;
int result = 0;
for (int i = 0;i < s.length(); i++) {
if(s.charAt(i) == '(') {
sk.push(i);
} else {
if (sk.empty()) {
start = i + 1;
} else {
sk.pop();
result = Math.max(result, sk.isEmpty() ? i - start + 1 : i - sk.peek());
}
}
}
return result;

}
}

// @note: scan direction: right pointer from start to end, left pointer from right pointer to start
public class Solution_start_to_end {

public int longestValidParentheses(String s) {

if (s == null || s.length() == 0) {
return 0;
}

int longest = 0;
int j = 1;

// this map will mark, from index=0 to position x, longest so far
// 注意，这里是保证 s[i][j]是连续的valid，所以才可以用 "i = j - skipLeft - 1;"来找左边的 '('
int[] longestSoFar = new int[s.length()];

while(j < s.length()) {

int skipLeft = longestSoFar[j - 1];
int i = j - skipLeft - 1; // to find left "("

// @note: I missed boundary check for i
// if (s.charAt(i) == '(' && s.charAt(j) == ')') {
if (i >= 0 && s.charAt(i) == '(' && s.charAt(j) == ')') {

longestSoFar[j] = j - i + 1; // @note: or, longestSoFar[j - 1] += 2;
// System.out.println(i + " " + j);

// probe previous valid segement
if (i - 1 >= 0 && longestSoFar[i - 1] > 0) {
longestSoFar[j] += longestSoFar[i - 1];
}

longest = Math.max(longest, longestSoFar[j]);
}

j++;
}

return longest;
}
}

// @note: scan direction: left pointer from end to start, right pointer from left pointer to end
public class Solution_end_to_start {
public int longestValidParentheses(String s) {

if (s == null || s.length() == 0)   return 0;

// 注意，这里是保证 s[i][j]是连续的valid，所以才可以用 "j = i + skip + 1;"来找右边的 '('
int[] dp = new int[s.length()];
int max = 0;

// scan from end to start
for (int i = s.length() - 2; i >= 0; i--) {

// check how many to skip
int skip = dp[i + 1];
int j = i + skip + 1;

// @note: i missed boundray check for j
if (j > s.length() - 1) {
continue;
}

if (s.charAt(i) == '(' && s.charAt(j) == ')') {
dp[i] = dp[i + 1] + 2;

// check position after j, eg: ))((()))()()((
if (j + 1 < s.length() && dp[j + 1] > 0)
dp[i] += dp[j + 1];

max = max > dp[i] ? max : dp[i];
}
}

return max;
}
}

// @note: 2-d dp array, over time
public int longestValidParentheses(String s) {

if (s == null || s.length() == 0) {
return 0;
}

int longest = Integer.MIN_VALUE;
int j = 0;

// marking, from i to j is valid parenthesis
boolean[][] dp = new boolean[s.length()][s.length()];

// @note: eg. ")()())", need another map to record previous longest valid
// this map will mark, at position x, longest so far
int[] longestSoFar = new int[s.length()];

while(j < s.length()) {

int i = 0;
while(i <= j) {

// check if valid
if ((s.charAt(i) == '(' && s.charAt(j) == ')') && (j - i <= 1 || dp[i + 1][j - 1])) {

dp[i][j] = true;
// System.out.println(i + " " + j);

// probe previous valid segement
int prev = i > 0 ? longestSoFar[i - 1] : 0;

// check longest
longest = Math.max(longest, j - i + 1 + prev);

// @note: record longest so far
longestSoFar[j] = longest;
}

i++;
}

j++;
}

return longest;
}

}

############

class Solution {
public int longestValidParentheses(String s) {
int n = s.length();
if (n < 2) {
return 0;
}
char[] cs = s.toCharArray();
int[] dp = new int[n];
int ans = 0;
for (int i = 1; i < n; ++i) {
if (cs[i] == ')') {
if (cs[i - 1] == '(') {
dp[i] = 2 + (i > 1 ? dp[i - 2] : 0);
} else {
int j = i - dp[i - 1] - 1;
if (j >= 0 && cs[j] == '(') {
dp[i] = 2 + dp[i - 1] + (j > 0 ? dp[j - 1] : 0);
}
}
ans = Math.max(ans, dp[i]);
}
}
return ans;
}
}

• // OJ: https://leetcode.com/problems/longest-valid-parentheses/
// Time: O(N)
// Space: O(N)
class Solution {
public:
int longestValidParentheses(string s) {
vector<int> dp(s.size() + 1, 0);
int ans = 0;
for (int i = 0; i < s.size(); ++i) {
if (s[i] == '(') continue;
int start = i - dp[i] - 1;
if (start >= 0 && s[start] == '(')
dp[i + 1] = dp[i] + 2 + dp[start];
ans = max(ans, dp[i + 1]);
}
return ans;
}
};

• 
class Solution:
def longestValidParentheses(self, s: str) -> int:
left = right = 0
res = 0
for c in s: # from left to right, '(()' => will never hit left==right
if c == '(':
left += 1
else:
right += 1
if left == right:
res = max(res, 2 * left)
if left < right:
left = right = 0

left = right = 0 # dont forget to reset
for c in reversed(s): # from right to left, '())' => will never hit left==right
if c == '(':
left += 1
else:
right += 1
if left == right:
res = max(res, 2 * left)
if left > right: # reverse '<' to '>'
left = right = 0

return res

class Solution:
def longestValidParentheses(self, s: str) -> int:
n = len(s)
if n < 2:
return 0
dp = [0] * n
for i in range(1, n):
if s[i] == ')':
if s[i - 1] == '(':
dp[i] = 2 + (dp[i - 2] if i > 1 else 0)
else:
j = i - dp[i - 1] - 1
if j >= 0 and s[j] == '(':
dp[i] = 2 + dp[i - 1] + dp[j - 1]
return max(dp)

############

class Solution(object):
def longestValidParentheses(self, s):
"""
:type s: str
:rtype: int
"""
dp = [0 for _ in range(0, len(s))]
left = 0
ans = 0
for i in range(0, len(s)):
if s[i] == "(":
left += 1
elif left > 0:
left -= 1
dp[i] = dp[i - 1] + 2
j = i - dp[i]
if j >= 0:
dp[i] += dp[j]
ans = max(ans, dp[i])
return ans


• func longestValidParentheses(s string) int {
n := len(s)
if n < 2 {
return 0
}
dp := make([]int, n)
ans := 0
for i := 1; i < n; i++ {
if s[i] == ')' {
if s[i-1] == '(' {
dp[i] = 2
if i > 1 {
dp[i] += dp[i-2]
}
} else {
j := i - dp[i-1] - 1
if j >= 0 && s[j] == '(' {
dp[i] = 2 + dp[i-1]
if j > 0 {
dp[i] += dp[j-1]
}
}
}
ans = max(ans, dp[i])
}
}
return ans
}

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

• using System.Collections.Generic;

public class Solution {
public int LongestValidParentheses(string s) {
var result = 0;
var baseCount = 0;
var stack = new Stack<int>();
foreach (var ch in s)
{
switch (ch)
{
case '(':
stack.Push(1);
break;
case ')':
if (stack.Count > 0)
{
var count = stack.Pop() + 1;
if (stack.Count > 0)
{
count += stack.Pop();
stack.Push(count);
if (count - 1 > result) result = count - 1;
}
else
{
baseCount += count;
if (baseCount > result) result = baseCount;
}
}
else
{
baseCount = 0;
}
break;
}
}
return result;
}
}

• function longestValidParentheses(s: string): number {
const n = s.length;
const f: number[] = new Array(n + 1).fill(0);
for (let i = 2; i <= n; ++i) {
if (s[i - 1] === ')') {
if (s[i - 2] === '(') {
f[i] = f[i - 2] + 2;
} else {
const j = i - f[i - 1] - 1;
if (j && s[j - 1] === '(') {
f[i] = f[i - 1] + 2 + f[j - 1];
}
}
}
}
return Math.max(...f);
}


• /**
* @param {string} s
* @return {number}
*/
var longestValidParentheses = function (s) {
const n = s.length;
const f = new Array(n + 1).fill(0);
for (let i = 2; i <= n; ++i) {
if (s[i - 1] === ')') {
if (s[i - 2] === '(') {
f[i] = f[i - 2] + 2;
} else {
const j = i - f[i - 1] - 1;
if (j && s[j - 1] === '(') {
f[i] = f[i - 1] + 2 + f[j - 1];
}
}
}
}
return Math.max(...f);
};