Why people give conclusion that this cannot be done with O(1) space?  my AC solution: O(n) run time, O(1) space
public class Solution {\n        public int longestValidParentheses(String s) {\n          return ltr(s, 0, s.length());\n        }\n    \n        public int lt
    public class Solution {\n        public int longestValidParentheses(String s) {\n          return ltr(s, 0, s.length());\n        }\n    \n        public int ltr(String s, int start, int end) {\n          int left = start;\n          int openLeft = 0;\n          int max = 0;\n          for(int i = start; i < end; i++) {\n            if(s.charAt(i) == '(')\n              openLeft++;\n            else\n              openLeft--;\n            if(openLeft < 0) {\n              int length = i - left;\n              if(length > max)\n                max = length;\n              left = i + 1;\n              openLeft = 0;\n            }\n          }\n          if(openLeft == 0) {\n            int length = end - left;\n            if(length > max)\n              max = length;\n          } {\n            int length = rtl(s, left, end);\n            if(length > max)\n              max = length;\n          }\n          return max;\n        }\n\n        public int rtl(String s, int start, int end) {\n          int right = end;\n          int openRight = 0;\n          int max = 0;\n          for(int i = end - 1; i >= start; i--) {\n            if(s.charAt(i) == ')')\n              openRight++;\n            else\n              openRight--;\n            if(openRight < 0) {\n              int length = right - (i + 1);\n              if(length > max)\n                max = length;\n              right = i;\n              openRight = 0;\n            }\n          }\n          if(openRight == 0) {\n            int length = right - start;\n            if(length > max)\n              max = length;\n          }\n          return max;\n        }\n      }\n\nI am pretty sure the code can be shorten to maybe half of the current size...... but why bother...\nThe idea is very simple, 2 iteration at most. First time from left to right, second time from right to left.\n\nThe second iteration is only needed if the first iteration has ends with unclosed left bracket.
[]