NC49 最长的括号子串
题目描述： 给出一个仅包含字符’(‘和’)'的字符串，计算最长的格式正确的括号子串的长度。 对于字符串"(()“来说，最长的格式正确的子串是”()"，长度为2. 再举一个例子：对于字符串")()())",来说，最长的格式正确的子串是"()()"，长度为4.

示例1

输入

“(()”

返回值

2

注意：连续有效的括号对数，不连续的不算

比如 (((())))(((()) 连续有效的括号对数 就是前四对 第九个 第十个 不能配对 所以后面的 两对 不能算是 连续有效的 这是小弟写的 水平有限 只能写出这样的了 当 字符串为 “(((())))(((())” 检测出是 6个 这是不对的 应该是四个 当字符串为"(((()))))((())" 时候 检测出是四个 这个是正确的

ps：“）（（（））（（）” 有效括号数 是正数第3到6个单括号 计算连续有效的括号数 是从第一个有效括号开始 直到 碰到第一个组不成一对括号的一个 单括号；所以这个是从正数第三个单括号开始计算 到第6个单括号 因为第7无法组成有效的成对括号 所以 从第7（包含7） 后的都不算。

#50%通过率,思路错误
def longestValidParentheses(s):
    count=0
    while '()' in s:
        s=s.replace('()','',1)
        count += 2
    return count
longestValidParentheses(")((())")

思路一：栈
思路1:通过进栈出栈的方式保存一些括号的index。这个stack，右括号想进去，只有可能是上一个stack顶部元素也是右，而第一个右括号怎么进？只能在stack为空的时候进，而且进还必须得连续进，否则只有把最新的左括号pop出来才能进。

与找到每个可能的子字符串后再判断它的有效性不同，我们可以用栈在遍历给定字符串的过程中去判断到目前为止扫描的子字符串的有效性，同时能的都最长有效字符串的长度。我们首先将 −1 放入栈顶。

对于遇到的每个(’ ，我们将它的下标放入栈中。

对于遇到的每个‘)’ ，我们弹出栈顶的元素并将当前元素的下标与弹出元素下标作差，得出当前有效括号字符串的长度。通过这种方法，我们继续计算有效子字符串的长度，并最终返回最长有效子字符串的长度。

#以下为第一种思路，通过栈来判断当前位置对应的括号是否符合有效长度
class Solution:
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        j = len(s)
        maxlen = 0
        #stack用来保存的是一些括号（不一定全是左，也不一定全是右）在s中的index
        stack = []
        #遍历index
        for i in range(j):
            #如果遇到一个右括号并且我们的stack里有东西可以pop出来
            #并且那个即将pop出来的东西是左括号，我们就pop
            if s[i] == ')' and len(stack) != 0 and s[stack[-1]] == '(':
                a = stack.pop()
                #如果pop完刚好 stack长度为0，说明这种情况是那种完全对称形的并且刚好结束一次有效括号的排列
                #则我们需要计算此时的maxlen
                if len(stack) == 0:
                    maxlen = i + 1
                #如果还有剩下的括号，我们则更新此时的最长长度
                else:
                    maxlen = max(maxlen, i - stack[-1])
 
            else:
                stack.append(i)
 
        return maxlen
sol=Solution()
sol.longestValidParentheses("(()))()")

思路：只在遇到左括号时放入栈中。这题是valid parentheses的扩展，也可以利用栈结构来实现。这里我们用栈存放左括号的下标，遇到左括号，将其下标存入栈中。遇到右括号，若此时栈为空，说明这个不是有效括号对里的，跳过，更新有效括号的起始点；若是栈不为空，则栈顶元素出栈。此时，若栈为空，后面不一定没有接合法的有效括号对，所以，计算当前和有效括号起始点的距离，并更新最大值，如：（）（）；若不为空，用当前位置距离栈顶元素的距离和maxlen中的最大值更新maxlen，如：（）（（）（）。

 
class Solution:
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        tl = len(s)
        stack = []
        st = 0
        maxlen = 0
        for i in range(tl):
            #如果是左括号，直接入stack
            if s[i] == '(':
                stack.append(i)
            #如果右括号
            else:
                #如果stack里没有元素匹对，说明有效括号已经结束，更新起始位置
                if len(stack) == 0:
                    st = i+1
                    continue
                #有元素匹对
                else:
                    a = stack.pop()
                    #pop出一个左括号匹对
                    #如果此时没了，不能保证不继续有效括号，所以根据当前的最长距离去更新maxlen
                    if len(stack) == 0:
                        maxlen = max(i - st+1, maxlen)
                    #如果此时还有 则计算与栈顶的索引相减来计算长度
                    else:
                        maxlen = max(i-stack[-1], maxlen)
 
        return maxlen
sol=Solution()
sol.longestValidParentheses("(()))()")

class Solution:
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        stack = [0]
        longest = 0
        for c in s:
            #若是左括号，列表添加0元素，若为右括号则弹出最后值之后，stack[-1]的元素值+2，就是合法括号长度
            if c == "(":
                stack.append(0)
            else:
                if len(stack) > 1:#通过列表长度控制是否重置列表并重新计算合法括号长度
                    val = stack.pop()#用索引值移除列表元素，默认为 index=-1，即val=最后一个值，同时弹出最后值。
                    stack[-1] += val + 2
                    longest = max(longest, stack[-1])#可能存在多个合法括号字串，所以比较他们的长度
                else:
                    stack = [0]
        return longest
sol=Solution()
sol.longestValidParentheses("(()))()")

#
# 
# @param s string字符串 
# @return int整型
#
class Solution:
    def longestValidParentheses(self , s ):
        # write code here
        stack = []
        pre_len = 0
        res = 0
        for i in range(len(s)):
            if s[i] == '(':
                stack.append(i-pre_len)
                pre_len = 0
            else:
                if stack:
                    pre_len = i - stack.pop() + 1
                    res = max(res, pre_len)
                else:
                    pre_len  = 0
        return res
sol=Solution()
sol.longestValidParentheses("(()))()")

#栈
class Solution:
    def longestValidParentheses(self, s):
        stack = [-1]
        ans = 0
        for i, ch in enumerate(s):
            if ch == "(":
                stack.append(i)
            else:
                if len(stack) > 1:
                    stack.pop()
                    ans = max(ans, i - stack[-1])
                else:
                    stack[-1] = i
        return ans
sol=Solution()
sol.longestValidParentheses("(()")

思路二：动态规划
这题还能使用动态规划的方式解：

dp[i]为到i处最长的有效括号，如果s[i]为左括号，则dp[i]为0，因为若字符串是以左括号结束，则不可能为有效的；若是为右括号，有两种情况：

一：其前者s[i-1]为左括号，所以dp[i]=dp[i-2]+2;

二、s[i-1]为右括号且s[i-dp[i-1]-1]为左括号，所以 dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2]，其中i-dp[i-1]-1对应对应最长括号的起始点

class Solution:
    def longestValidParentheses(self, s):
        
        a =len(s)
        if a <2:
            return 0
        maxlen =0
        #dp[i]表示刚好在s[i]以前（包括s[i]在内)的最长括号长度
        #如果s[i] = '(', dp[i] = 0
        dp =[0 for i in range(a)]
        for i in range(1, a):
          #当前i的对称点的索引
            pos =i -1-dp[i-1]
            if s[i]==')' and s[i-1] =='(' and i -2>=0:
              #等于前前项的最长长度+2
                dp[i] =dp[i-2] +2
            elif s[i] ==')' and pos >=0 and s[pos] =='(':  
              #等于上个对称点+2
                dp[i] =dp[i-1] +2
   
            if pos -1>=0:
          #如果对称点前还有长度，则加上那段长度
                dp[i] +=dp[i-dp[i-1]-2]
        return max(dp)
sol=Solution()
sol.longestValidParentheses("()(()")

#不正确
class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        lens = len(s)
        dp = [0 for x in range (lens+1)]
        for i in range(2,lens):
            if s[i] == ")" and s[i- dp[i-1] - 1]=="(":
                dp[i] = dp[i-1]+dp[i-dp[i-1]-2] + 2
        return dp[-1]
sol=Solution()
sol.longestValidParentheses("()(()")

#双指针计数
class Solution:
    def longestValidParentheses(self, s):
        ans = 0

        # 正向遍历
        left = right = 0
        for ch in s:
            if ch == "(":
                left += 1
            else:
                right += 1
                if left == right:
                    ans = max(ans, right * 2)
                elif left < right:
                    left = 0
                    right = 0

        # 反向遍历
        left = right = 0
        for ch in s[::-1]:
            if ch == "(":
                left += 1
                if left == right:
                    ans = max(ans, left * 2)
                elif left > right:
                    left = 0
                    right = 0
            else:
                right += 1

        return ans
sol=Solution()
sol.longestValidParentheses("()(()")