<p>Given a string containing just the characters <code>&#39;(&#39;</code> and <code>&#39;)&#39;</code>, return <em>the length of the longest valid (well-formed) parentheses </em><span data-keyword="substring-nonempty"><em>substring</em></span>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;(()&quot;
<strong>Output:</strong> 2
<strong>Explanation:</strong> The longest valid parentheses substring is &quot;()&quot;.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;)()())&quot;
<strong>Output:</strong> 4
<strong>Explanation:</strong> The longest valid parentheses substring is &quot;()()&quot;.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;&quot;
<strong>Output:</strong> 0
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>0 &lt;= s.length &lt;= 3 * 10<sup>4</sup></code></li>
	<li><code>s[i]</code> is <code>&#39;(&#39;</code>, or <code>&#39;)&#39;</code>.</li>
</ul>

class Solution:

# Using a Stack
#
    def longestValidParentheses(self, s: str) -> int:
        maxlen = 0
        stack = []
        stack.append(-1)

        for i in range(len(s)):
            if s[i] == '(':
                stack.append(i)
            else:
                stack.pop()
                if not stack:
                    stack.append(i)
                else:
                    maxlen = max(maxlen, i - stack[-1])
        return maxlen


# Using Dynamic Programming
#
#    def longestValidParentheses(self, s: str) -> int:
#        # s = "())((())"
#        # s = '))()()('
#        maxlen = 0
#        dp = [0] * len(s)
#
#        for i in range(1, len(s)):
#            # Only valid if ends in ")"
#            if s[i] == ")":
#                if s[i - 1] == "(":
#                    # Ends with "...()"
#                    dp[i] = (dp[i - 2] if i >= 2 else 0) + 2
#                elif i - dp[i - 1] > 0 and s[i - dp[i - 1] - 1] == "(":
#                    # Ends with "...))"
#                    dp[i] = (
#                        dp[i - 1]
#                        + (dp[i - dp[i - 1] - 2] if i - dp[i - 1] >= 2 else 0)
#                        + 2
#                    )
#
#            maxlen = max(maxlen, dp[i])
#
#        print("maxlen:", maxlen, ", dp:", dp)
#        return maxlen


# Brute force
#
#     def isValid(self, s: str) -> bool:
#         stack = []
#         for char in s:
#             if char == '(':
#                 stack.append('(')
#             elif stack and stack[-1] == '(':
#                 stack.pop()
#             else:
#                 return False
#         return len(stack) == 0
#
#
#     def longestValidParentheses(self, s: str) -> int:
#         maxlen = 0
#         for i in range(len(s)):
#             for j in range(i + 2, len(s) + 1, 2):
#                 if self.isValid(s[i:j]):
#                     maxlen = max(maxlen, j - i)
#         return maxlen
#

17000