Python/C++/Go O(n) by stack [w/ Comment]
\u4E2D\u6587\u8A73\u89E3 \u89E3\u984C\u6587\u7AE0\n\nO(n) by stack\n\n---\n\nImplementation by stack in Python\n\n\nclass Solution:\n    def longestValidParenth
[\u4E2D\u6587\u8A73\u89E3 \u89E3\u984C\u6587\u7AE0](https://vocus.cc/article/651e40a5fd89780001b42f30)\n\nO(n) by stack\n\n---\n\n**Implementation** by stack in Python\n\n```\nclass Solution:\n    def longestValidParentheses(self, s: str) -> int:\n\n        # stack, used to record index of parenthesis\n        # initialized to -1 as dummy head for valid parentheses length computation\n        stack = [-1]\n        \n        max_length = 0\n        \n\t\t# linear scan each index and character in input string s\n        for cur_idx, char in enumerate(s):\n            \n            if char == \'(\':\n                \n                # push when current char is (\n                stack.append( cur_idx )\n                \n            else:\n                \n                # pop when current char is )\n                stack.pop()\n                \n                if not stack:\n                    \n                    # stack is empty, push current index into stack\n                    stack.append( cur_idx )\n                else:\n                    # stack is non-empty, update maximal valid parentheses length\n                    max_length = max(max_length, cur_idx - stack[-1])\n                \n        return max_length\n```\n\n---\n\n**Implementation** by stack in C++\n\n```\nclass Solution {\npublic:\n    int longestValidParentheses(string s) {\n        \n        // Initialized a stack with -1 on the bottom\n        std::stack<int> _stack = std::stack<int>( {-1} );\n        \n        int maxSize = 0;\n        \n        // scan each character\n        for( int i = 0 ; i < s.length() ;  i++ ){\n            \n            char ch = s[i];\n            \n            if( ch == \'(\' ){\n                \n                // current charachter is left bracket\n                _stack.push( i );\n                \n            }else{\n                \n                // right charachter is left bracket\n                _stack.pop();\n                \n                if( _stack.empty() ){\n                    \n                    // handle for corner case when ) comes before (\n                    _stack.push( i );\n                    \n                }else{\n                    // update max length if we have paired bracket\n                    maxSize = max( maxSize, i - _stack.top() );    \n                }\n            }\n        }\n        \n        return maxSize;\n        \n    }\n};\n```\n\n---\n\n**Implementation** by stack in Go\n\n```\n// Support function max\nfunc Max(a, b int)int{\n    \n    if a > b{\n        return a\n    }\n    \n    return b\n}\n\n\nfunc longestValidParentheses(s string) int {\n    \n    // stack, used to record index of parenthesis\n    // initialized to -1 as dummy head for valid parenthesis length computation\n    stack := []int{-1}\n    \n    maxLength := 0\n    \n    // linear scan each index and character in input string s\n    for curIdx, char := range s{\n        \n        if char == \'(\'{\n            \n            // push when current char is (\n            stack = append( stack, curIdx)\n            \n        }else{\n            \n            // pop when current char is )\n            stack = stack[:len(stack)-1]\n            \n            if len(stack)==0{\n                \n                // stack is empty, push current index into stack\n                stack = append( stack, curIdx)\n            }else{\n                \n                // stack is non-empty, update maximal valud parentheses length\n                \n                maxLength = Max( maxLength, curIdx - stack[ len(stack)-1 ] )\n            }\n            \n        }\n        \n    }\n    \n    return maxLength\n    \n}\n\n```\n\n---\n\nRelated leetcode challenge:\n\n[Leetcode #20 Valid Parentheses](https://leetcode.com/problems/valid-parentheses/)
['String', 'Stack', 'C', 'Python', 'C++', 'Go', 'Python3']