1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
/**
 * Find the length of the longest valid parentheses substring.
 * Stack-Based approach.
 * 
 * @param {string} s - The input string containing only '(' and ')'
 * @return {number} - The length of the longest valid parentheses substring
 */
function longestValidParenthesesStack(s) {
  const n = s.length;
  const stack = [-1];  // Initialize with -1 as a base for calculating lengths
  let maxLength = 0;
  
  for (let i = 0; i < n; i++) {
    if (s[i] === '(') {
      stack.push(i);
    } else {  // s[i] === ')'
      stack.pop();
      if (stack.length === 0) {
        stack.push(i);  // New base
      } else {
        maxLength = Math.max(maxLength, i - stack[stack.length - 1]);
      }
    }
  }
  
  return maxLength;
}
 
/**
 * Find the length of the longest valid parentheses substring.
 * Dynamic Programming approach.
 * 
 * @param {string} s - The input string containing only '(' and ')'
 * @return {number} - The length of the longest valid parentheses substring
 */
function longestValidParenthesesDP(s) {
  const n = s.length;
  const dp = new Array(n).fill(0);
  let maxLength = 0;
  
  for (let i = 1; i < n; i++) {
    if (s[i] === ')') {
      if (s[i - 1] === '(') {
        // Case: "()"
        dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
      } else if (i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] === '(') {
        // Case: "))" where there's a matching "(" for the first ")"
        dp[i] = dp[i - 1] + 2 + (i - dp[i - 1] >= 2 ? dp[i - dp[i - 1] - 2] : 0);
      }
      
      maxLength = Math.max(maxLength, dp[i]);
    }
  }
  
  return maxLength;
}
 
/**
 * Find the length of the longest valid parentheses substring.
 * Two-Pass approach.
 * 
 * @param {string} s - The input string containing only '(' and ')'
 * @return {number} - The length of the longest valid parentheses substring
 */
function longestValidParenthesesTwoPass(s) {
  const n = s.length;
  let left = 0, right = 0;
  let maxLength = 0;
  
  // First pass: left to right
  for (let i = 0; i < n; i++) {
    if (s[i] === '(') {
      left++;
    } else {
      right++;
    }
    
    if (left === right) {
      maxLength = Math.max(maxLength, left + right);
    } else if (right > left) {
      left = right = 0;
    }
  }
  
  // Reset counters
  left = right = 0;
  
  // Second pass: right to left
  for (let i = n - 1; i >= 0; i--) {
    if (s[i] === '(') {
      left++;
    } else {
      right++;
    }
    
    if (left === right) {
      maxLength = Math.max(maxLength, left + right);
    } else if (left > right) {
      left = right = 0;
    }
  }
  
  return maxLength;
}
 
// Test cases
console.log(longestValidParenthesesStack("(()"));  // 2
console.log(longestValidParenthesesStack(")()())"));  // 4
console.log(longestValidParenthesesStack(""));  // 0
 
console.log(longestValidParenthesesDP("(()"));  // 2
console.log(longestValidParenthesesDP(")()())"));  // 4
console.log(longestValidParenthesesDP(""));  // 0
 
console.log(longestValidParenthesesTwoPass("(()"));  // 2
console.log(longestValidParenthesesTwoPass(")()())"));  // 4
console.log(longestValidParenthesesTwoPass(""));  // 0