<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:
    def longestValidParentheses(self, s: str) -> int:
        res = []
        left = right = 0
        left_cnt = right_cnt = 0
        cur_length = 0
        stack = []
        while left < len(s) and right < len(s):
            c = s[right]
            if c == '(':
                stack.append(right)
                left_cnt += 1
            else:
                if left_cnt:
                    res.append((stack.pop(), right))
                    left_cnt -= 1
                else:
                    left = right + 1
                    left_cnt = right_cnt = 0
            right += 1
        if not res:
            return 0
        res.sort()
        print(res)
        ans = [res[0]]
        for i in range(1, len(res)):
            left, right = res[i][0], res[i][1]
            prev_left, prev_right = ans[-1][0], ans[-1][1]
            if left < prev_left and right > prev_right:
                ans[-1] = (left, right)
            elif left >= prev_left and right <= prev_right:
                continue
            else:
                if prev_right + 1 == left:
                    ans[-1] = (prev_left, right)
                else:
                    ans.append((left, right))
        print(ans)
        max_length = length = ans[0][1] - ans[0][0] + 1
        # print(length)
        for i in range(1, len(ans)):
            left = ans[i][0]
            right = ans[i][1]
            prev_right = ans[i - 1][1]
            if prev_right + 1 == left:
                length += right - left + 1
                # print(length)
                max_length = max(max_length, length)
            else:
                length = right - left + 1
                # print(length)
                max_length = max(max_length , length)
        return max_length
                    
            
        
17900