Longest Valid Parentheses – Leetcode Python

LeetCode has a Hard coding Problem in Its’ Algorithm Section “Longest Valid Parentheses”. Today We are going to solve this problem. LeetCode Link of the Problem is HERE

Longest Valid Parentheses

Question

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

Examples

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

Constraints:

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

Solution to Longest Valid Parentheses

Skeleton Code given in Leetcode is

class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        

1. Method violence taken every substring O (N ^ 2), then use the method in question 20 determines whether it is legally O (N), the total time of O (N ^ 3).

2. Violence Solution traversed for one string O (N), from each character, the total number of the left bracket and a right bracket number, and length of each record satisfies the O (N) when the number of left and right bracket == Numbers in parentheses, if left Number of parentheses <number of right parentheses, continue. The time complexity is O(N^2).

3. Stack local stack process with the longest substring matching simulation, after again traversing, namely matching the rest of the stack is not on the brackets, between which the string position, i.e. to meet the requirements, which take a longest. O(N).

Complete Solution

class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        stack=[]
        for i in xrange(len(s)):
            if s[i]=='(' or not stack:
                stack.append(i)
            else:
                t=stack.pop()
                if s[t] == ')':
                    stack.append(t)
                    stack.append(i)
        right,longest=len(s),0
        while stack:
            left=stack.pop()
            longest=max(longest,right-left-1)
            right=left
        return max(longest,right)

READ MORE

Python-related posts Visit HERE

C++ related posts Visit HERE

Databases related posts Visit HERE

Data Structures related posts visit HERE

Algorithms related posts visit HERE

Data Science related posts visit HERE

Share the Knowledge