Given a string consisting of opening and closing parenthesis, find length of the longest valid parenthesis substring.<\/p>\n
Examples:<\/p>\n
Input : ((()\r\nOutput : 2\r\nExplanation : ()\r\n\r\nInput: )()())\r\nOutput : 4\r\nExplanation: ()() \r\n\r\nInput: ()(()))))\r\nOutput: 6\r\nExplanation: ()(()))\r\n<\/pre>\n[ad type=\u201dbanner\u201d]\nWe strongly recommend you to minimize your browser and try this yourself first.<\/b><\/p>\n
A Simple Approach<\/strong> is to find all the substrings of given string. For every string, check if it is a valid string or not. If valid and length is more than maximum length so far, then update maximum length. We can check whether a substring is valid or not in linear time using a stack (See this for details). Time complexity of this solution is O(n2<\/sup>.<\/p>\n
An Efficient Solution<\/strong> can solve this problem in O(n) time. The idea is to store indexes of previous starting brackets in a stack. The first element of stack is a special element that provides index before beginning of valid substring (base for next valid string).<\/p>\n
1) Create an empty stack and push -1 to it. The first element\r\n of stack is used to provide base for next valid string. \r\n\r\n2) Initialize result as 0.\r\n\r\n3) If the character is '(' i.e. str[i] == '('), push index \r\n 'i' to the stack. \r\n \r\n2) Else (if the character is ')')\r\n a) Pop an item from stack (Most of the time an opening bracket)\r\n b) If stack is not empty, then find length of current valid\r\n substring by taking difference between current index and\r\n top of the stack. If current length is more than result,\r\n then update the result.\r\n c) If stack is empty, push current index as base for next\r\n valid substring.\r\n\r\n3) Return result.<\/pre>\n[ad type=\u201dbanner\u201d]\nBelow are C++ \u00a0implementations of above algorithm.<\/p>\n
C++ Programming:<\/strong><\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%2F%2F%20C%2B%2B%20program%20to%20find%20length%20of%20the%20longest%20valid%0A%2F%2F%20substring%0A%23include%3Cbits%2Fstdc%2B%2B.h%3E%0Ausing%20namespace%20std%3B%0A%20%0Aint%20findMaxLen(string%20str)%0A%7B%0A%20%20%20%20int%20n%20%3D%20str.length()%3B%0A%20%0A%20%20%20%20%2F%2F%20Create%20a%20stack%20and%20push%20-1%20as%20initial%20index%20to%20it.%0A%20%20%20%20stack%3Cint%3E%20stk%3B%0A%20%20%20%20stk.push(-1)%3B%0A%20%0A%20%20%20%20%2F%2F%20Initialize%20result%0A%20%20%20%20int%20result%20%3D%200%3B%0A%20%0A%20%20%20%20%2F%2F%20Traverse%20all%20characters%20of%20given%20string%0A%20%20%20%20for%20(int%20i%3D0%3B%20i%3Cn%3B%20i%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20opening%20bracket%2C%20push%20index%20of%20it%0A%20%20%20%20%20%20%20%20if%20(str%5Bi%5D%20%3D%3D%20\u2032(\u2018)%0A%20%20%20%20%20%20%20%20%20%20stk.push(i)%3B%0A%20%0A%20%20%20%20%20%20%20%20else%20%2F%2F%20If%20closing%20bracket%2C%20i.e.%2Cstr%5Bi%5D%20%3D%20\u2019)\u2019%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Pop%20the%20previous%20opening%20bracket\u2019s%20index%0A%20%20%20%20%20%20%20%20%20%20%20%20stk.pop()%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Check%20if%20this%20length%20formed%20with%20base%20of%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20current%20valid%20substring%20is%20more%20than%20max%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20so%20far%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(!stk.empty())%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20result%20%3D%20max(result%2C%20i%20-%20stk.top())%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20If%20stack%20is%20empty.%20push%20current%20index%20as%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20base%20for%20next%20valid%20substring%20(if%20any)%0A%20%20%20%20%20%20%20%20%20%20%20%20else%20stk.push(i)%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20return%20result%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%0Aint%20main()%0A%7B%0A%20%20%20%20string%20str%20%3D%20%22((()()%22%3B%0A%20%20%20%20cout%20%3C%3C%20findMaxLen(str)%20%3C%3C%20endl%3B%0A%20%0A%20%20%20%20str%20%3D%20%22()(()))))%22%3B%0A%20%20%20%20cout%20%3C%3C%20findMaxLen(str)%20%3C%3C%20endl%20%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n
Output:<\/strong><\/p>\n
4\r\n6<\/pre>\n[ad type=\u201dbanner\u201d]\nExplanation with example:<\/strong><\/p>\n
Input: str = \"(()()\"\r\n\r\nInitialize result as 0 and stack with one item -1.\r\n\r\nFor i = 0, str[0] = '(', we push 0 in stack\r\n\r\nFor i = 1, str[1] = '(', we push 1 in stack\r\n\r\nFor i = 2, str[2] = ')', currently stack has [-1, 0, 1], we pop\r\nfrom the stack and the stack now is [-1, 0] and length of current\r\nvalid substring becomes 2 (we get this 2 by subtracting stack top \r\nfrom current index).\r\nSince current length is more than current result, we update result.\r\n\r\nFor i = 3, str[3] = '(', we push again, stack is [-1, 0, 3].\r\n\r\nFor i = 4, str[4] = ')', we pop from the stack, stack becomes \r\n[-1, 0] and length of current valid substring becomes 4 (we get \r\nthis 4 by subtracting stack top from current index). \r\nSince current length is more than current result, we update result.<\/pre>\n","protected":false},"excerpt":{"rendered":"C++ Algorithm – Length of the longest valid sub string – Stack – Given a string consisting of opening and closing parenthesis.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,73012,79607],"tags":[81547,81549,81545,81544,81543,81546,81548,81550],"class_list":["post-27416","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-data-structures","category-stack","tag-balanced-parentheses-dynamic-programming","tag-find-the-longest-substring-without-any-number-and-at-least-one-upper-case-character","tag-longest-subsequence-of-balanced-parentheses","tag-longest-parentheses-substring-java","tag-longest-valid-parentheses-leetcode-c","tag-longest-valid-parentheses-youtube","tag-modify-the-array","tag-you-are-given-a-string-s-consisting-of-n-brackets"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27416","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27416"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27416\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27416"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27416"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27416"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}