<p>Given a parentheses string <code>s</code> containing only the characters <code>&#39;(&#39;</code> and <code>&#39;)&#39;</code>. A parentheses string is <strong>balanced</strong> if:</p>

<ul>
	<li>Any left parenthesis <code>&#39;(&#39;</code> must have a corresponding two consecutive right parenthesis <code>&#39;))&#39;</code>.</li>
	<li>Left parenthesis <code>&#39;(&#39;</code> must go before the corresponding two consecutive right parenthesis <code>&#39;))&#39;</code>.</li>
</ul>

<p>In other words, we treat <code>&#39;(&#39;</code> as an opening parenthesis and <code>&#39;))&#39;</code> as a closing parenthesis.</p>

<ul>
	<li>For example, <code>&quot;())&quot;</code>, <code>&quot;())(())))&quot;</code> and <code>&quot;(())())))&quot;</code> are balanced, <code>&quot;)()&quot;</code>, <code>&quot;()))&quot;</code> and <code>&quot;(()))&quot;</code> are not balanced.</li>
</ul>

<p>You can insert the characters <code>&#39;(&#39;</code> and <code>&#39;)&#39;</code> at any position of the string to balance it if needed.</p>

<p>Return <em>the minimum number of insertions</em> needed to make <code>s</code> balanced.</p>

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

<pre>
<strong>Input:</strong> s = &quot;(()))&quot;
<strong>Output:</strong> 1
<strong>Explanation:</strong> The second &#39;(&#39; has two matching &#39;))&#39;, but the first &#39;(&#39; has only &#39;)&#39; matching. We need to add one more &#39;)&#39; at the end of the string to be &quot;(())))&quot; which is balanced.
</pre>

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

<pre>
<strong>Input:</strong> s = &quot;())&quot;
<strong>Output:</strong> 0
<strong>Explanation:</strong> The string is already balanced.
</pre>

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

<pre>
<strong>Input:</strong> s = &quot;))())(&quot;
<strong>Output:</strong> 3
<strong>Explanation:</strong> Add &#39;(&#39; to match the first &#39;))&#39;, Add &#39;))&#39; to match the last &#39;(&#39;.
</pre>

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

<ul>
	<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>
	<li><code>s</code> consists of <code>&#39;(&#39;</code> and <code>&#39;)&#39;</code> only.</li>
</ul>

class Solution:
    def minInsertions(self, s: str) -> int:
        count = 0

        def fix_odd_runs_right_par(string):
            nonlocal count
            rc = 0
            for i in range(len(string)-1, -1, -1):
                c = string[i]
                if c == '(':
                    if (rc % 2) == 1:
                        string = string[:i+1] + ')' + string[i+1:]
                        count += 1
                    rc = 0
                elif c == ')':
                    rc += 1

            if (rc % 2) == 1:
                string = ')' + string
                count += 1

            return string


        def fix_rightmost_left_par(string):
            nonlocal count 
            pos = string.rfind('(')
            if pos == -1:
                return True, string

            if pos == len(string)-1:
                count += 2
                string = string[:pos]
            # elif pos == len(string)-2:
            #     count += 1
            #     string = string[:pos]
            else:
                count += 0
                string = string[:pos] + string[pos+3:]

            return False, string



        def fix_remaining_right_par(string):
            nonlocal count
            count += ( len(string) // 2 ) 


        
        s = fix_odd_runs_right_par(s)

        done = False
        while not done:
            done, s = fix_rightmost_left_par(s)

        fix_remaining_right_par(s)

        return count








        
17800