<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:
        if len(s) == 0:
            return 0

        # ((())))))()  )(  ()(())()))))()()()(((()))
        left = 0
        right = 0
        # True means it can connect with next 
        lens = []
        curr_len = 0 
        for i, ch in enumerate(s):
            if ch == "(":
                left += 1
            else:
                right += 1
                # check if there is anything to pop and check if it can connect to prev
                
                if left > 0 or (len(lens) > 0 and lens[-1][1] > 0):
                    
                    left -= 1
                    right -= 1
                    if len(lens) > 0:
                        print("debug", lens)
                        prev, prev_left, prev_right = lens.pop()
                        if prev_left > 0 and prev_right == 0 and left == -1: # merge to prev chunk
                            print("0", lens)
                            lens.append((prev + 2, prev_left - 1, prev_right))
                            left = 0
                            print("1", lens)
                        else: #unable to merge to previous chunk 
                            lens.append((prev, prev_left, prev_right))
                            lens.append((2, left, right))
                            left = 0

                    else: 
                        lens.append((2, left, right))
                        left = 0

                    while len(lens) > 1:
                        curr, curr_left, curr_right = lens.pop()
                        prev, prev_left, prev_right = lens.pop()
                        if curr_left == 0 and prev_right == 0:
                            print("chunk merge")
                            lens.append((curr + prev, prev_left, curr_right))
                        else:  # unable to merge 
                            lens.append((prev, prev_left, prev_right))
                            lens.append((curr, curr_left, curr_right))
                            break
                else:  # nothing to pop on left for now, seq ends with more right.
                    if len(lens) > 0:
                        prev, prev_left, prev_right = lens.pop()
                        lens.append((prev, prev_left, prev_right+1))
                    right = 0

        # lens.append((2, left == 0, right == 0))
        # while len(lens) > 1:
        #     curr, curr_connect_left, curr_connect_right = lens.pop()
        #     prev, prev_connect_left, prev_connect_right = lens.pop()
        #     if curr_connect_left and prev_connect_right:
        #         lens.append(curr + prev, prev_connect_left, curr_connect_right)
        #     else:  # unable to merge 
        #         lens.append(prev, prev_connect_left, prev_connect_right)
        #         lens.append(curr, curr_connect_left, curr_connect_right)
        if len(lens) == 0:
            return 0
        return max([num for num, left, right in lens])


16900