7ms 100% O(n) time & O(1) space, without stack or array
This solution is inspired by maximum sum of subsequence.\n\t- Let\'s recall the O(n) solution for that problem: we give up when the current sum < 0, set the sum
- This solution is inspired by maximum sum of subsequence.\n\t- Let\'s recall the O(n) solution for that problem: we give up when the current sum < 0, set the sum = 0 and restart counting from the next number; and we records the maximum all the time.\n\t- In this problem, I use sum to indicate whether the expression is balanced:\n\t\t- +1 to represent \'(\' and -1 for \')\'; if sum == 0, then the substring is balanced;\n\t\t- sum < 0 means the expression is unbalanced, where I give up the current length and start again.\n\t- However, when we scan from left side, we can only find the expression unbalanced when \')\' appears too often, and \'(\' should also be checked for balance, so we should scan again from right side.\n\t- Total time complexity is O(n) as we scanned 2 times, and space complexity is O(1) as we don\'t record things in an array or stack:)\n```java\n\tpublic int longestValidParenthesesOnline(String s) {\n        if (s == null) return -1;\n        if (s.length() == 0) return 0;\n        char[] str = s.toCharArray();\n        int sum = 0, res = 0, len = 0, n = s.length();\n\t\t// Scan the string from left side, plus 1 for \'(\' and minus 1 for \')\'.\n        for (int i = 0; i < n; i++) {\n            if (str[i] == \'(\') sum++;\n            else sum--;\n            if (sum < 0) {\n                sum = 0;\n                len = 0;\n            } else {\n                len++;\n                if (sum == 0) res = Math.max(res, len);\n            }\n        }\n\t\t// Scan again from right side, plus 1 for \')\' and minus 1 for \'(\'.\n        sum = 0;\n        len = 0;\n        for (int i = n - 1; i >= 0; i--) {\n            if (str[i] == \')\') sum++;\n            else sum--;\n            if (sum < 0) {\n                sum = 0;\n                len = 0;\n            } else {\n                len++;\n                if (sum == 0) res = Math.max(res, len);\n            }\n        }\n        return res;\n    }
[]