O(n) one pass solution without stacks
Basically it is a two pass solution, but I can combine them in one loop.\n\nFirst, scan from left to right while checking the balance. Second, scan from right t
Basically it is a two pass solution, but I can combine them in one loop.\n\nFirst, scan from left to right while checking the balance. Second, scan from right to left in the same way. So no stack is needed.\n\n    class Solution {\n    public:\n        int longestValidParentheses(string s) {\n            int result = 0;\n            {\n                int left = 0;\n                int right = 0;\n                for (int i = 0; i < s.length(); i++) {\n                    switch (s[i]) {\n                    case '(': left++; break;\n                    case ')': right++; break;\n                    default: left = right = 0; continue;\n                    }\n                    if (left == right && left + right > result) result = left + right;\n                    if (right > left) left = right = 0;\n                }\n            }\n            {\n                int left = 0;\n                int right = 0;\n                for (int i = s.length(); i > 0; i--) {\n                    switch (s[i-1]) {\n                    case '(': left++; break;\n                    case ')': right++; break;\n                    default: left = right = 0; continue;\n                    }\n                    if (left == right && left + right > result) result = left + right;\n                    if (left > right) left = right = 0;\n                }\n            }\n            return result;\n        }\n    };\n\nCombination:\n\n    class Solution {\n    public:\n        int longestValidParentheses(string s) {\n            int result = 0;\n            int ll = 0, lr = 0, li = 0;  // left paren sum, right paren sum, left index\n            int rl = 0, rr = 0, ri = s.length();  // left paren sum, right paren sum, right index\n            while (li < s.length() && ri > 0) {\n                switch (s[li]) {\n                case '(': ll++; break;\n                case ')': lr++; break;\n                default: ll = lr = 0;\n                }\n                switch (s[ri-1]) {\n                case '(': rl++; break;\n                case ')': rr++; break;\n                default: rl = rr = 0;\n                }\n                if (ll == lr && ll + lr > result) result = ll + lr;\n                if (rl == rr && rl + rr > result) result = rl + rr;\n                if (ll < lr) ll = lr = 0;\n                if (rl > rr) rl = rr = 0;\n                li++; ri--;\n            }\n            return result;\n        }\n    };
[]