✅ Guide to 4 Solutions: Stack, Mark & Count, O(1) Space Two-Pass, DP 🔥 Python3
1. Stack Single Pass, O(N) time, O(N) space\n- Why Stack: \n    -  Use stack to store the positions of unmatched opening brackets \'(\'. \n    - If we see a \')
## 1. Stack Single Pass, O(N) time, O(N) space\n- Why Stack: \n    -  Use stack to store the positions of unmatched opening brackets \'(\'. \n    - If we see a \')\', the stack allows us to quickly find and match the most recent \'(\'. \n    - This process enables immediate calculation of the length of the current valid substring by using the indices stored in the stack.\n- Stack Initialization: \n    - The stack is never empty; stack[0] serves as an initial boundary to help calculate lengths of valid substrings. It is not necessarily the left bound of any valid substring, but rather a reference point to calculate lengths when valid substrings are found. \n    - The stack starts with -1 to handle cases where the valid substring begins at the start of the string.\n- Main Loop\n    - For \'(\', push the current index onto the stack.\n    - For \')\', pop the stack to find the matching \'(\':\n        - If the stack becomes empty, it means there was no matching \'(\' for this \')\', so we push the current index as a new left boundary for future substrings.\n        - If the stack is not empty, it means that we just popped the index of a \'(\', and a new matching pair \'( )\' is found. \n            - After popping, stack[-1] is either\n                -  the index of the last unmatched \'(\' or \n                - the left boundary of the current valid substring, which can be -1 or the index of an invalid \')\'.\n            - The length of the current valid substring spans from the character just after the index at stack[-1] to the current index i. \n### stack solution with comments\n```python\nclass Solution:\n    def longestValidParentheses(self, s: str) -> int:\n        # Stack to keep track of indices. The first element is initialized to -1\n        # to handle edge cases where the valid substring starts from the beginning.\n        stack = [-1]\n        max_length = 0\n\n        for i, c in enumerate(s):\n            if c == \'(\':\n                stack.append(i)\n            else:\n                # Index of the last unmatched \'(\'\n                stack.pop()\n                if not stack:\n                    # Stack is empty, meaning there was no matching \'(\'\n                    # Push the current index as the new base\n                    stack.append(i)\n                else:\n                    # Stack is not empty, meaning we have found a matching pair\n                    # After popping, stack[-1] is either the index of the last unmatched \'(\' or\n                    # the left boundary of the current valid substring,\n                    # which can be -1, or the index of an invalid \')\'. \n                    # Current substring spans from stack[-1] + 1 to i. \n                    max_length = max(max_length, i - stack[-1])\n\n        return max_length\n```\n### stack solution clean version\n```python\nclass Solution:\n    def longestValidParentheses(self, s: str) -> int:\n        stack = [-1]\n        max_length = 0\n\n        for i, c in enumerate(s):\n            if c == \'(\':\n                stack.append(i)\n            else:\n                stack.pop()\n                if not stack:\n                    stack.append(i)\n                else:\n                    max_length = max(max_length, i - stack[-1])\n\n        return max_length\n```\n### Stack Example Walkthrough\n```\ns = ") ( ( ) ) ", stack = [-1], max_len = 0\n\n1. i = 0,  ") ( ( ) )", s[0] = \')\'\n            ^ \n   - stack.pop() -> stack = []        # no match found\n   - stack.append(i) -> stack = [0]   # new left boundary\n\n2. i = 1,  ") ( ( ) )", s[1] = \'(\'\n              ^ \n   - stack.append(i) -> stack = [0, 1]        \n   \n3. i = 2,  ") ( ( ) )", s[2] = \'(\'\n                ^ \n   - stack.append(i) -> stack = [0, 1, 2]       \n\n4. i = 3,  ") ( ( ) )", s[3] = \')\'\n                  ^ \n   - stack.pop() -> stack = [0, 1]                         # match found\n   - max_len = max(max_len, i - stack[-1]) = 3 - 1 = 2     # stack[-1] is the last unmatched \'(\'\n\n5. i = 4,  ") ( ( ) )", s[4] = \')\'\n                    ^ \n   - stack.pop() -> stack = [0]                            # match found\n   - max_len = max(max_len, i - stack[-1]) = 4 - 0 = 4     # stack[-1] is the left bound, the invalid \')\'\n\n6. return max_len = 4\n```\n## 2. Stack + Marks & Count, O(N) time, O(N) space\n- Main Idea: Transform all matching "( )" pair into 1s, then find the longest consecutive 1s. \n- Initialization: \n    - Use a stack to store the positions of unmatched opening brackets \'(\'.\n    - Use an marks array to mark positions of matched parentheses, initialized to zeros.\n- First Loop:\n    - For \'(\', push the current index onto the stack.\n    - For \')\' and if the stack is not empty, \n        - Pop the stack to get the index of the matching \'(\'. \n        - Mark the positions of both \'(\' and \')\' in the ones array by setting them to 1.\n- Second Loop:\n    - Find the longest consecutive ones, which represents the longest valid parentheses substring.\n  \n### Stack + Marks & Count Solution With Comments\n```python\nclass Solution:\n    def longestValidParentheses(self, s: str) -> int:\n        match_marks = [0] * len(s)     # 0: no match, 1: match found\n        stack = []              # Stack to keep track of indices of unmatched \'(\'\n        max_length = 0 \n\n        # First pass: mark matching parentheses\n        for i, c in enumerate(s):\n            if c == \'(\':\n                stack.append(i)     # \'(\' not matched yet, push to stack\n            elif stack:\n                match_i = stack.pop() \n                match_marks[match_i] = 1   # Mark the position of matched \'(\' as 1\n                match_marks[i] = 1         # Mark the position of matched \')\' as 1\n\n        # Second pass: find the longest consecutive ones\n        current_length = 0\n        for mark in match_marks:\n            if mark == 1:\n                current_length += 1  \n            else:\n                current_length = 0 \n            max_length = max(max_length, current_length) \n\n        return max_length\n\n```\n## 3. Two Pass Scan, O(N) time, O(1) space\n- 1st pass: \n    -  Scans from left to right, and counts the number of \'(\' and \')\' encountered.\n    - When the counts of \'(\' and \')\' are equal, it means a valid substring is found, and the maximum length is updated .\n    - If the count of \')\' exceeds the count of \'(\', it resets the counts because a valid substring cannot continue past this point.\n    - Works for: Balanced sequences like "( ( ) )" resulting in a valid length update.\n    - Cannot handle: Unmatched opening parentheses at the end, \n        - e.g. For "( ( ) (", counts are not equal at any time, so maximum length is not updated.\n- 2nd pass: \n    - Scans the string from right to left, can also be done by reversing a string and going left to right.\n    - When the counts of \'(\' and \')\' are equal, update maximum length.\n    - If the count of \'(\' exceeds the count of \')\', resets the counts, opposite from the 1st pass. This is opposite from the first pass because we are scanning in reverse order. \n    - Works for: Unmatched opening sequences at the end, \n        - e.g. When reversed, "( ( ) " -> ") ( ( ", now counts are equal at i = 1, so maximum length can be updated. \n### Two Pass solution with comments\n```python\nclass Solution:\n    def longestValidParentheses(self, s: str) -> int:\n        max_length = 0\n        left = 0    # number of \'(\'\n        right = 0   # number of \')\'\n\n        # First pass: left to right\n        for c in s:\n            if c == \'(\':\n                left += 1\n            else:\n                right += 1\n\n            if left == right:       # Valid, so update max_len\n                max_length = max(max_length, 2 * right)\n            elif left < right:      # More \')\' than \'(\', invalid, reset counts\n                left = right = 0    \n\n        left = right = 0\n\n        # Second pass: right to left\n        for i in range(len(s)-1, -1, -1):\n            if s[i] == \'(\':\n                left += 1\n            else:\n                right += 1\n\n            if left == right:\n                max_length = max(max_length, 2 * left)\n            elif left > right:      # More \'(\' than \')\', invalid, reset counts\n                left = right = 0\n\n        return max_length\n```\n\n## 4. Dynamic Programming, 1 pass, O(N) time, O(N) space\n- Why DP: Overlapping subproblems\n    -  The solution to the problem at each position in the string depends on solutions to previous positions. Specifically, the length of the longest valid substring ending at a particular position depends on the lengths of valid substrings ending at previous positions.  \n- Initialization:\n    - dp: list of zeros of length n . dp[i] stores the length of the longest valid parentheses substring ending at index i.\n- Main Loop: \n    - If the current character is \')\' and the previous character is \'(\':\n        - This forms a basic "( )" pair.\n        - The length of this valid substring is 2 plus any valid substring length ending just before this pair.\n    - If the current character is \')\' and the previous character is also \')\':\n        - Look for the matching \'(\' for the current \')\'.\n        - Calculate the index where this matching \'(\' should be.\n        - If a valid matching \'(\' is found, add the lengths of valid substrings before and after this matching pair to get the total length.\n### DP solution with detailed comments\n```python\nclass Solution:\n    def longestValidParentheses(self, s: str) -> int:\n        n = len(s)\n        dp = [0] * n            # dp[i]: length of longest valid substring ending at i\n        max_len = 0             # Length of the overall longest valid substring\n        \n        for i in range(1, n):\n            if s[i] == \'(\':     # Can\'t end a valid substring with \'(\'\n                continue\n            \n            # s[i] == \')\' \n            # Case 1: prev is \'(\', forming a valid "()" pair\n            # prev_len: length of valid substring ending two indices before\n            # continue the previous substring if possible\n            if s[i-1] == \'(\':      \n                prev_len = dp[i-2] if i >= 2 else 0     \n                dp[i] = prev_len + 2    \n            else:           \n            # Case 2: prev is \')\', look for a matching \'(\' for current \')\'\n            # matching_idx: index of the potential matching \'(\'\n            # e.g. s = "(())", i = 3, dp[i-1] = 2 (length of "()"), matching_idx = 0\n            #                ... ... ( ...  ... )\n            #                   ^    ^     ^    ^\n            #                   |    |     |    i\n            #                   |    |   dp[i-1]\n            #                   |  matching_idx\n            #             prev_len: length of valid substring ending at matching_idx - 1 if exist\n                matching_idx = i - dp[i-1] - 1              \n                if matching_idx >= 0 and s[matching_idx] == \'(\':\n                    prev_len = dp[matching_idx-1] if matching_idx > 0 else 0\n                    # combine: prev two substrings and the new pair "()" together                  \n                    dp[i] = prev_len + dp[i-1] + 2\n            \n            max_len = max(max_len, dp[i])  \n        \n        return max_len\n```\n\n### DP solution clean version\n```python\nclass Solution:\n    def longestValidParentheses(self, s: str) -> int:\n        dp = [0] * len(s)\n\n        for i in range(1, len(s)):\n            if s[i] == \')\':\n                if s[i-1] == \'(\':\n                    dp[i] = (dp[i-2] if i > 1 else 0) + 2\n                else:\n                    matching_idx = i - dp[i-1] - 1\n                    if matching_idx >= 0 and s[matching_idx] == \'(\':\n                        dp[i] = dp[i-1] + (dp[matching_idx-1] if matching_idx > 0 else 0) + 2   \n                \n        return max(dp) if dp else 0\n```\n\n### DP Example Walkthrough\n```\ns = "( ) ( ( ) ) ", dp = [0, 0, 0, 0, 0, 0], max_len = 0\n\n# start at i = 1 because dp[0] will always be 0\n\n1. i = 1,  "( ) ( ( ) )", s[1] = \')\'\n              ^ \n   - case 1: "()", \n        i < 2: prev_len = 0 \n        dp[1] = prev_len + 2 = 2\n   - dp = [0, 2, 0, 0, 0, 0], max_len = 2\n   \n2. i = [2, 3]: skip opening parentheses\n\n3. i = 4, "( ) ( ( ) )", s[4] = \')\'\n                   ^\n   - Case 1: "()", prev_len = dp[3] = 0\n        dp[4] = prev_len + 2 = 2\n   - dp = [0, 2, 0, 0, 2, 0], max_len = 2\n\n4. i = 5, "( ) ( ( ) )", s[5] = \')\'\n                     ^\n   - Case 2: "(...)", dp[4] = 2\n        matching_idx = i - dp[4] - 1 = 5 - 2 - 1 = 2 \n        dp[5] = 2 + 0 + 2 = 4 \n   - dp = [0, 2, 0, 0, 2, 4], max_len = 4\n\n5. return max_len = 4\n```\n\n\n\n
['String', 'Dynamic Programming', 'Stack', 'Python3']