<p>You are given a string <code>s</code> that consists of lower case English letters and brackets.</p>

<p>Reverse the strings in each pair of matching parentheses, starting from the innermost one.</p>

<p>Your result should <strong>not</strong> contain any brackets.</p>

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

<pre>
<strong>Input:</strong> s = &quot;(abcd)&quot;
<strong>Output:</strong> &quot;dcba&quot;
</pre>

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

<pre>
<strong>Input:</strong> s = &quot;(u(love)i)&quot;
<strong>Output:</strong> &quot;iloveu&quot;
<strong>Explanation:</strong> The substring &quot;love&quot; is reversed first, then the whole string is reversed.
</pre>

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

<pre>
<strong>Input:</strong> s = &quot;(ed(et(oc))el)&quot;
<strong>Output:</strong> &quot;leetcode&quot;
<strong>Explanation:</strong> First, we reverse the substring &quot;oc&quot;, then &quot;etco&quot;, and finally, the whole string.
</pre>

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

<ul>
	<li><code>1 &lt;= s.length &lt;= 2000</code></li>
	<li><code>s</code> only contains lower case English characters and parentheses.</li>
	<li>It is guaranteed that all parentheses are balanced.</li>
</ul>

class Solution:
    def reverseParentheses(self, s: str) -> str:
        """
        What is a naive way?
        Reverse string for every parenthesis
        (ed(et(oc))el)
        le((co)te)de
        leet(oc)de
        leetcode
        - runtime: O(n^2)

        Better way? Maybe recursive function
        - reverse function every time you see parenthesis, two pointer approach
        (u(love)i)
        
        stack = [uevoli] -> returns iloveu
        stack = [love] -> returns evol

        (e(et(oc)d)el)
        stack = [edocteel] -> returns leetcode
        stack = [etcod] -> returns docte
        stack = [oc] -> returns co

                   i
        subs = "(ed(et(oc))el)", res = "ed", return "leetcode" and i + 1
                           i
        subs = "(ed(et(oc))el)", res = "etco", return "octe" and i + 1
                          i
        subsn = "(ed(et(oc))el)", res = "oc", return "co" and i + 1
        
        def reverse(subs: str) -> str:
            - create empty string
            - loop through subs
                - when "(" is identified then recurse again and add returned
                    - add returned to i
                - when ")" is identified then break loop
                - otherwise add char
                    - add 1 to i
            - reverse string and return string and last index
        """

        def reverse(s, i):
            res = ""
            while i < len(s):
                if s[i] == "(":
                    res_s, j = reverse(s, i+1)
                    res, i = res + res_s, j
                elif s[i] == ")":
                    return res[::-1], i + 1
                else:
                    res += s[i]
                    i += 1

            return res, i+1

        res, _ = reverse(s, 0)
        return res
16300