Skip to content
The Chat Archive
vicuna-33b Arena Human Preference 55K

Given a string containing just the characters '(' and ')', return the length of the…

  1. User

    Given a string containing just the characters '(' and ')', return the length of the longest valid (well-formed) parentheses substring .

    Example 1:

    Input: s = "(()" Output: 2 Explanation: The longest valid parentheses substring is "()".

    Example 2:

    Input: s = ")()())" Output: 4 Explanation: The longest valid parentheses substring is "()()".

    Example 3:

    Input: s = "" Output: 0

    Constraints:

    0 <= s.length <= 3 * 104
    s[i] is '(', or ')'.
    

    complete this class class Solution: def longestValidParentheses(self, s: str) -> int:

  2. Assistant

    You can complete the class by implementing the longestValidParentheses function using dynamic programming. Here's a possible implementation:

    class Solution:
        def longestValidParentheses(self, s: str) -> int:
            if not s:
                return 0
    
            left_paren, right_paren = 0, 0
            max_length = 0
            for i, c in enumerate(s):
                if c == '(':
                    left_paren += 1
                elif c == ')':
                    right_paren += 1
                    if left_paren == right_paren:
                        max_length = max(max_length, i - left_paren + 1)
                    left_paren = 0
    
            return max_length
    

    This implementation iterates through the input string and keeps track of the number of open parentheses ('(') and closed parentheses (')'). When an open parentheses is encountered, the left_paren counter is incremented. When a closed parentheses is encountered, the right_paren counter is incremented. If the number of open parentheses equals the number of closed parentheses, it means that we have a valid parentheses substring, and the function calculates its length. The maximum length found is returned as the final answer.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.