Given a string consisting of opening and closing parenthesis, find the length of the longest balanced parenthesis in it.

((**()()**

**(()())**(()

(((**()**

((((

**()()**

A simple solution is to generate all substrings of the given string and for each substring, check if it is balanced or not. If the substring is balanced and has more length than the maximum length balanced substring found so far, we update the result. The time complexity of this solution is `O(n ^{3})` since there are

`O(n`substrings and each substring takes

^{2})`O(n)`time to check if it is balanced.

We can solve this problem in `O(n)` time using `O(n)` space. The idea is to iterate over characters of the string and if the current character is an opening parenthesis, we push its index in a stack. If the current character is an closing parenthesis, we pop the top index from the stack and push the current index into the stack if the stack becomes empty.

We can get length of the longest balanced parenthesis ending at current character (closing parenthesis) by finding difference between the current index and the index at top of the stack. We keep track of the length of the longest balanced parenthesis and update it whenever required.

For example, below table demonstrates the above operations for the string `(()())(()`. Note the stack initially contains -1, to handle the case when balanced parenthesis starts from index 0.

The algorithm can be implemented as follows in C++:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
#include <iostream> #include <stack> using namespace std; // Function to find length of the longest balanced parenthesis in a string int findMaxLen(string str) { // create a stack of integers for storing index of parenthesis in the string stack<int> stack; // initialize the stack by -1 stack.push(-1); // stores the length of the longest balanced parenthesis int len = 0; // iterate over characters of the string for (int i = 0; i < str.length(); i++) { // if current character is an opening parenthesis, // push its index in the stack if (str[i] == '(') { stack.push(i); } // if current character is a closing parenthesis else { // pop top index from the stack stack.pop(); // if the stack becomes empty, push current index into the stack if (stack.empty()) { stack.push(i); continue; } // get length of the longest balanced parenthesis ending // at current character int curr_len = i - stack.top(); // update length of longest balanced parenthesis if required if (len < curr_len) len = curr_len; } } return len; } int main() { cout << findMaxLen("((()()") << endl; // prints 4 cout << findMaxLen("(((()") << endl; // prints 2 cout << findMaxLen("((((") << endl; // prints 0 cout << findMaxLen("()()") << endl; // prints 4 cout << findMaxLen("(()())(()"); // prints 6 return 0; } |

**Thanks for reading.**

Please use our online compiler to post code in comments. To contribute, get in touch with us.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply