My solution using one stack in one pass
Since any valid parentheses sequence starts from a '(' and ends at ')', we can calculate new length when we meet a ')'. The key is to use a stack to store all t
Since any valid parentheses sequence starts from a '(' and ends at ')', we can calculate new length when we meet a ')'. The key is to use a stack to store all the indices and the start position is always the one on top of the stack. See the code below for details.\n\n\n     // Using a stack. One pass\n        int longestValidParentheses(string s) {\n            vector<int> stack;\n            int maxLen = 0;\n            for (int i = 0; i < s.size(); ++i)\n            {\n                if (s[i] == '(')\n                    stack.push_back(i);\n                else {\n                    if (!stack.empty() && s[stack.back()] == '(') {\n                        stack.pop_back();\n                        int lastPos = -1;\n                        if (!stack.empty())\n                            lastPos = stack.back();\n                        int curLen = i - lastPos;\n                        maxLen = (maxLen < curLen) ? curLen : maxLen;\n                    } else\n                        stack.push_back(i);\n                }\n            }\n            return maxLen;\n        }
['Stack']