C++ O(n) time and O(1) space (0ms runtime beats 100%) - explained
Intuition\n\nBefore explaining the solution, I will write how I came up with the solution.\n\nThe main point to notice in this problem is that the moment we get
### Intuition\n\nBefore explaining the solution, I will write how I came up with the solution.\n\nThe main point to notice in this problem is that the moment we get an invalid parenthesis, the subarray can\'t start from beyond this point.\nNot clear ? Let\'s understand with an example.\n\nConsider this simple string.\n```()()))()(())```, at index 4 the subarray starting from index 0 becomes invalid, it is clear the longest valid parenthesis won\'t start from [0, 3] and end after 4.\n\nThis striked me that I can use a sliding window to solve this problem.\n\n### How to solve ?\n\nConsider a window with left end shown by **i** and right end shown by **j**.\nInitially **i = 0 and j = 0**\nLet us consider another variable k which will help us to determine when subarray becomes invalid.\n\nNow, we start moving j keeping i as fixed. \n\nIncrement k when we encounter ```(``` and decrement when we encounter ```)```.\n\nWhenever k becomes zero we will update our answer with max(ans,  j - i + 1)\nIt is clear when k becomes negative the subarray will become invalid, so we will move the left end i.e **i** to the new position.\n\n**Question**\nWhy are we updating the answer when k is 0 and not when k > 0.\n**Answer**\nWe know for sure, whenever we get k as 0 the subarray is valid and length will be j - i + 1.\nBut when k > 0 the subarray is still valid, but the length will be less than j - i + 1.\nBut ofcourse we are missing some values, since the length which is less j - i + 1 can be a better answer.\n\nConsider this string ```(()```. Here, we will never get k = 0 and hence we can\'t update our answer.\n\n**How to resolve this?**\nWe have to repeat the above process but this time starting i = n - 1 and j = n - 1. Now, keep moving j to the left side and do the same as above. Here k will increase when we encounter ```)``` and decrease when we encounter ```(```.\n\n### Cpp Code\n\n```\nclass Solution {\npublic:\n    int longestValidParentheses(string s) {\n        int n = s.length(), i = 0, ans = 0, k = 0;\n        for(int j = 0; j < n; j++) {\n            if(s[j] == \'(\')  k++;\n            else if(s[j] == \')\') {\n                k--;\n                if(k == 0)\n                    ans = max(ans, j - i + 1);\n            }\n            if(k < 0) {\n                k = 0;\n                i = j + 1;\n            }\n        }\n        k = 0, i = n - 1;\n        for(int j = n - 1; j >= 0; j--) {\n            if(s[j] == \')\') {\n                k++;\n            }\n            else if(s[j] == \'(\') {\n                k--;\n                if(k == 0)\n                    ans = max(ans, i - j + 1);\n            }\n            if(k < 0) {\n                k = 0;\n                i = j - 1;\n            }\n        }\n        return ans;\n    }\n};\n```\n\n**Please upvote if this post is helpful to you :)**
['C', 'Sliding Window']