Find length of the longest balanced parenthesis in a string

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


 

For example, the longest balanced parenthesis is highlighted in below expressions:


((()()
(()())(()
(((()
((((
()()

 
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(n3) since there are O(n2) substrings and each substring takes 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.

Length of the longest balanced parenthesis

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

 

Download   Run Code

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

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

avatar
  Subscribe  
Notify of