Skip to main content

Length of the longest balanced parentheses in a string

The problem is to find the length of the longest balanced parentheses substring in a given expression. A balanced parentheses substring is a substring of the expression that contains only '(' and ')' characters and is properly balanced. For a substring to be balanced, each opening parenthesis must have a corresponding closing parenthesis in the substring, and the order of opening and closing should be correct.

Problem Statement

Given a string containing only '(' and ')' characters, we need to find the length of the longest balanced parentheses substring.

Example

Consider the following examples:

  1. Input: "()))()())"
    • Stack: [-1, 0, 1]
    • Remove top element from the stack (1), calculate the count (i - record.peek()) = 2 - 1 = 1, which is less than the current length.
    • Remove top element from the stack (0), calculate the count (i - record.peek()) = 3 - 0 = 3, which is greater than the current length. Update length to 3.
    • Stack: [-1, 0]
    • Remove top element from the stack (0), calculate the count (i - record.peek()) = 7 - 0 = 7, which is greater than the current length. Update length to 7.
    • Stack: [-1]
    • Remove top element from the stack (-1), calculate the count (i - record.peek()) = 9 - (-1) = 10, which is greater than the current length. Update length to 10.
    • Stack: (empty)
    • Result: Length of the longest balanced parentheses substring is 10.

Idea to Solve the Problem

To find the length of the longest balanced parentheses substring, we can use a stack to keep track of the indices of opening parentheses. We initialize a variable length to store the maximum length of the balanced parentheses substring. We also initialize a variable count to calculate the length of the current balanced parentheses substring.

We iterate through the expression from left to right. For each character, if it is an opening parenthesis '(', we push its index into the stack. If it is a closing parenthesis ')', we pop the top element from the stack, which represents the index of the last unmatched opening parenthesis. We calculate the length of the current balanced parentheses substring by subtracting the current index from the index at the top of the stack. If the current length is greater than the length, we update the length with the current length.

After iterating through the entire expression, the length will contain the maximum length of the balanced parentheses substring.

Pseudocode

Function lengthLongestBParentheses(expression):
    Set length to 0
    Set n to the length of expression
    If n > 0:
        Create an empty stack called record
        Push -1 into record
        Set count to -1
        For i from 0 to n-1:
            If expression[i] is ')':
                Pop from record
                If record is not empty:
                    Set count to i - record.peek()
                    If count > length:
                        Set length to count
                Else:
                    Push i into record
            Else if expression[i] is '(':
                Push i into record
            Else:
                // Invalid expression 
                Return
    Display "Given expression: " + expression
    Display "Length: " + length

Algorithm

  1. Create a class called BalancedParentheses.
  2. Define a function called lengthLongestBParentheses which takes the input string expression.
  3. Initialize a variable length to 0 to store the maximum length of the balanced parentheses substring.
  4. Get the length n of the input expression.
  5. If the length n is greater than 0, create an empty stack called record to store the indices of opening parentheses.
  6. Push -1 into the stack record to mark the starting index.
  7. Initialize a variable count to -1 to calculate the length of the current balanced parentheses substring.
  8. Iterate through the input expression from left to right using a for loop with index i ranging from 0 to n-1. a. If the current character expression[i] is ')':
    • Pop the top element from the stack record, which represents the index of the last unmatched opening parenthesis.
    • If the stack record is not empty, calculate the length of the current balanced parentheses substring as count = i - record.peek().
      • If count is greater than the current length, update length with count.
    • If the stack record is empty, push the current index i into the stack to mark a new starting index for the next potential balanced substring. b. If the current character expression[i] is '(', push the current index i into the stack record. c. If the current character is neither '(' nor ')', it means the expression is invalid, so return.
  9. After the for loop, length will contain the maximum length of the balanced parentheses substring.
  10. Display the given expression and the calculated length.

Code Solution

import java.util.Stack;
/*
    Java program for
    Length of the longest balanced parentheses in a string
*/
public class BalancedParentheses
{
	public void lengthLongestBParentheses(String expression)
	{
		int length = 0;
		// Get the length of expression which is contains 
		// open and close parentheses.
		int n = expression.length();
		if (n > 0)
		{
			Stack < Integer > record = new Stack < Integer > ();
			int count = -1;
			record.push(-1);
			for (int i = 0; i < n; ++i)
			{
				if (expression.charAt(i) == ')')
				{
					// Remove top element
					record.pop();
					if (record.isEmpty() == false)
					{
						// When record not empty
						count = i - record.peek();
						if (count > length)
						{
							length = count;
						}
					}
					else
					{
						// When stack empty then insert current location
						record.push(i);
					}
				}
				else if (expression.charAt(i) == '(')
				{
					// Add current location
					record.push(i);
				}
				else
				{
					// Invalid expression 
					return;
				}
			}
		}
		// Display given expression
		System.out.println(" Given expression : " + expression);
		// Display calculated result
		System.out.println(" Length : " + length);
	}
	public static void main(String[] args)
	{
		BalancedParentheses task = new BalancedParentheses();
		// "()))()())"
		//      ----
		// Ans 4
		task.lengthLongestBParentheses("()))()())");
		// ")()))((()))((()("
		//       ------
		// Ans 6
		task.lengthLongestBParentheses(")()))((()))((()(");
		// ")))((("
		// Ans 0
		task.lengthLongestBParentheses(")))(((");
	}
}

Output

 Given expression : ()))()())
 Length : 4
 Given expression : )()))((()))((()(
 Length : 6
 Given expression : )))(((
 Length : 0
// Include header file
#include <iostream>
#include <stack>
#include <string>

using namespace std;
/*
    C++ program for
    Length of the longest balanced parentheses in a string
*/
class BalancedParentheses
{
	public: void lengthLongestBParentheses(string expression)
	{
		int length = 0;
		// Get the length of expression which is contains 
		// open and close parentheses.
		int n = expression.length();
		if (n > 0)
		{
			stack < int > record;
			int count = -1;
			record.push(-1);
			for (int i = 0; i < n; ++i)
			{
				if (expression[i] == ')')
				{
					// Remove top element
					record.pop();
					if (record.empty() == false)
					{
						// When record not empty
						count = i - record.top();
						if (count > length)
						{
							length = count;
						}
					}
					else
					{
						// When stack empty then insert current location
						record.push(i);
					}
				}
				else if (expression[i] == '(')
				{
					// Add current location
					record.push(i);
				}
				else
				{
					// Invalid expression 
					return;
				}
			}
		}
		// Display given expression
		cout << " Given expression : " << expression << endl;
		// Display calculated result
		cout << " Length : " << length << endl;
	}
};
int main()
{
	BalancedParentheses *task = new BalancedParentheses();
	// "()))()())"
	//      ----
	// Ans 4
	task->lengthLongestBParentheses("()))()())");
	// ")()))((()))((()("
	//       ------
	// Ans 6
	task->lengthLongestBParentheses(")()))((()))((()(");
	// ")))((("
	// Ans 0
	task->lengthLongestBParentheses(")))(((");
	return 0;
}

Output

 Given expression : ()))()())
 Length : 4
 Given expression : )()))((()))((()(
 Length : 6
 Given expression : )))(((
 Length : 0
// Include namespace system
using System;
using System.Collections.Generic;
/*
    Csharp program for
    Length of the longest balanced parentheses in a string
*/
public class BalancedParentheses
{
	public void lengthLongestBParentheses(String expression)
	{
		int length = 0;
		// Get the length of expression which is contains 
		// open and close parentheses.
		int n = expression.Length;
		if (n > 0)
		{
			Stack < int > record = new Stack < int > ();
			int count = -1;
			record.Push(-1);
			for (int i = 0; i < n; ++i)
			{
				if (expression[i] == ')')
				{
					// Remove top element
					record.Pop();
					if ((record.Count == 0) == false)
					{
						// When record not empty
						count = i - record.Peek();
						if (count > length)
						{
							length = count;
						}
					}
					else
					{
						// When stack empty then insert current location
						record.Push(i);
					}
				}
				else if (expression[i] == '(')
				{
					// Add current location
					record.Push(i);
				}
				else
				{
					// Invalid expression 
					return;
				}
			}
		}
		// Display given expression
		Console.WriteLine(" Given expression : " + expression);
		// Display calculated result
		Console.WriteLine(" Length : " + length);
	}
	public static void Main(String[] args)
	{
		BalancedParentheses task = new BalancedParentheses();
		// "()))()())"
		//      ----
		// Ans 4
		task.lengthLongestBParentheses("()))()())");
		// ")()))((()))((()("
		//       ------
		// Ans 6
		task.lengthLongestBParentheses(")()))((()))((()(");
		// ")))((("
		// Ans 0
		task.lengthLongestBParentheses(")))(((");
	}
}

Output

 Given expression : ()))()())
 Length : 4
 Given expression : )()))((()))((()(
 Length : 6
 Given expression : )))(((
 Length : 0
package main
import "fmt"
/*
    Go program for
    Length of the longest balanced parentheses in a string
*/

func lengthLongestBParentheses(expression string) {
	var length int = 0
	// Get the length of expression which is contains 
	// open and close parentheses.
	var n int = len(expression)
	if n > 0 {
		var record = make([]int,0);
		var count int = -1
		record = append(record, -1)
		for i := 0 ; i < n ; i++ {
			if expression[i] == ')' {
				// Remove top element
				record = record[: len(record) - 1]
				if len(record) > 0 {
					// When record not empty
					count = i - record[len(record) - 1]
					if count > length {
						length = count
					}
				} else {
					// When stack empty then insert current location
					record = append(record, i)
				}
			} else if expression[i] == '(' {
				// Add current location
				record = append(record, i)
			} else {
				// Invalid expression 
				return
			}
		}
	}
	// Display given expression
	fmt.Println(" Given expression : ", expression)
	// Display calculated result
	fmt.Println(" Length : ", length)
}
func main() {
	
	// "()))()())"
	//      ----
	// Ans 4
	lengthLongestBParentheses("()))()())")
	// ")()))((()))((()("
	//       ------
	// Ans 6
	lengthLongestBParentheses(")()))((()))((()(")
	// ")))((("
	// Ans 0
	lengthLongestBParentheses(")))(((")
}

Output

 Given expression :  ()))()())
 Length :  4
 Given expression :  )()))((()))((()(
 Length :  6
 Given expression :  )))(((
 Length :  0

<?php
/*
    Php program for
    Length of the longest balanced parentheses in a string
*/
class BalancedParentheses
{
	public	function lengthLongestBParentheses($expression)
	{
		$length = 0;
		// Get the length of expression which is contains 
		// open and close parentheses.
		$n = strlen($expression);
		if ($n > 0)
		{
			$record = array();
			$count = -1;
			array_push($record, -1);
			for ($i = 0; $i < $n; ++$i)
			{
				if ($expression[$i] == ')')
				{
					// Remove top element
					array_pop($record);
					if (empty($record) == false)
					{
						// When record not empty
						$count = $i - end($record);
						if ($count > $length)
						{
							$length = $count;
						}
					}
					else
					{
						// When stack empty then insert current location
						array_push($record, $i);
					}
				}
				else if ($expression[$i] == '(')
				{
					// Add current location
					array_push($record, $i);
				}
				else
				{
					// Invalid expression 
					return;
				}
			}
		}
		// Display given expression
		echo(" Given expression : ".$expression."\n");
		// Display calculated result
		echo(" Length : ".$length."\n");
	}
}

function main()
{
	$task = new BalancedParentheses();
	// "()))()())"
	//      ----
	// Ans 4
	$task->lengthLongestBParentheses("()))()())");
	// ")()))((()))((()("
	//       ------
	// Ans 6
	$task->lengthLongestBParentheses(")()))((()))((()(");
	// ")))((("
	// Ans 0
	$task->lengthLongestBParentheses(")))(((");
}
main();

Output

 Given expression : ()))()())
 Length : 4
 Given expression : )()))((()))((()(
 Length : 6
 Given expression : )))(((
 Length : 0
/*
    Node JS program for
    Length of the longest balanced parentheses in a string
*/
class BalancedParentheses
{
	lengthLongestBParentheses(expression)
	{
		var length = 0;
		// Get the length of expression which is contains 
		// open and close parentheses.
		var n = expression.length;
		if (n > 0)
		{
			var record = [];
			var count = -1;
			record.push(-1);
			for (var i = 0; i < n; ++i)
			{
				if (expression.charAt(i) == ')')
				{
					// Remove top element
					record.pop();
					if ((record.length == 0) == false)
					{
						// When record not empty
						count = i - record[record.length - 1];
						if (count > length)
						{
							length = count;
						}
					}
					else
					{
						// When stack empty then insert current location
						record.push(i);
					}
				}
				else if (expression.charAt(i) == '(')
				{
					// Add current location
					record.push(i);
				}
				else
				{
					// Invalid expression 
					return;
				}
			}
		}
		// Display given expression
		console.log(" Given expression : " + expression);
		// Display calculated result
		console.log(" Length : " + length);
	}
}

function main()
{
	var task = new BalancedParentheses();
	// "()))()())"
	//      ----
	// Ans 4
	task.lengthLongestBParentheses("()))()())");
	// ")()))((()))((()("
	//       ------
	// Ans 6
	task.lengthLongestBParentheses(")()))((()))((()(");
	// ")))((("
	// Ans 0
	task.lengthLongestBParentheses(")))(((");
}
main();

Output

 Given expression : ()))()())
 Length : 4
 Given expression : )()))((()))((()(
 Length : 6
 Given expression : )))(((
 Length : 0
#    Python 3 program for
#    Length of the longest balanced parentheses in a string
class BalancedParentheses :
	def lengthLongestBParentheses(self, expression) :
		length = 0
		#  Get the length of expression which is contains 
		#  open and close parentheses.
		n = len(expression)
		if (n > 0) :
			record = []
			count = -1
			record.append(-1)
			i = 0
			while (i < n) :
				if (expression[i] == ')') :
					#  Remove top element
					record.pop()
					if ((len(record) == 0) == False) :
						#  When record not empty
						count = i - record[-1]
						if (count > length) :
							length = count
						
					else :
						#  When stack empty then insert current location
						record.append(i)
					
				elif (expression[i] == '(') :
					#  Add current location
					record.append(i)
				else :
					#  Invalid expression 
					return
				
				i += 1
			
		
		#  Display given expression
		print(" Given expression : ", expression)
		#  Display calculated result
		print(" Length : ", length)
	

def main() :
	task = BalancedParentheses()
	#  "()))()())"
	#       ----
	#  Ans 4
	task.lengthLongestBParentheses("()))()())")
	#  ")()))((()))((()("
	#        ------
	#  Ans 6
	task.lengthLongestBParentheses(")()))((()))((()(")
	#  ")))((("
	#  Ans 0
	task.lengthLongestBParentheses(")))(((")

if __name__ == "__main__": main()

Output

 Given expression :  ()))()())
 Length :  4
 Given expression :  )()))((()))((()(
 Length :  6
 Given expression :  )))(((
 Length :  0
#    Ruby program for
#    Length of the longest balanced parentheses in a string
class BalancedParentheses 
	def lengthLongestBParentheses(expression) 
		length = 0
		#  Get the length of expression which is contains 
		#  open and close parentheses.
		n = expression.length
		if (n > 0) 
			record = []
			count = -1
			record.push(-1)
			i = 0
			while (i < n) 
				if (expression[i] == ')') 
					#  Remove top element
					record.pop()
					if ((record.length == 0) == false) 
						#  When record not empty
						count = i - record.last
						if (count > length) 
							length = count
						end

					else
 
						#  When stack empty then insert current location
						record.push(i)
					end

				elsif (expression[i] == '(') 
					#  Add current location
					record.push(i)
				else
 
					#  Invalid expression 
					return
				end

				i += 1
			end

		end

		#  Display given expression
		print(" Given expression : ", expression, "\n")
		#  Display calculated result
		print(" Length : ", length, "\n")
	end

end

def main() 
	task = BalancedParentheses.new()
	#  "()))()())"
	#       ----
	#  Ans 4
	task.lengthLongestBParentheses("()))()())")
	#  ")()))((()))((()("
	#        ------
	#  Ans 6
	task.lengthLongestBParentheses(")()))((()))((()(")
	#  ")))((("
	#  Ans 0
	task.lengthLongestBParentheses(")))(((")
end

main()

Output

 Given expression : ()))()())
 Length : 4
 Given expression : )()))((()))((()(
 Length : 6
 Given expression : )))(((
 Length : 0

import scala.collection.mutable._;
/*
    Scala program for
    Length of the longest balanced parentheses in a string
*/
class BalancedParentheses()
{
	def lengthLongestBParentheses(expression: String): Unit = {
		var length: Int = 0;
		// Get the length of expression which is contains 
		// open and close parentheses.
		var n: Int = expression.length();
		if (n > 0)
		{
			var record: Stack[Int] = new Stack[Int]();
			var count: Int = -1;
			record.push(-1);
			var i: Int = 0;
			while (i < n)
			{
				if (expression.charAt(i) == ')')
				{
					// Remove top element
					record.pop;
					if (record.isEmpty == false)
					{
						// When record not empty
						count = i - record.top;
						if (count > length)
						{
							length = count;
						}
					}
					else
					{
						// When stack empty then insert current location
						record.push(i);
					}
				}
				else if (expression.charAt(i) == '(')
				{
					// Add current location
					record.push(i);
				}
				else
				{
					// Invalid expression 
					return;
				}
				i += 1;
			}
		}
		// Display given expression
		println(" Given expression : " + expression);
		// Display calculated result
		println(" Length : " + length);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: BalancedParentheses = new BalancedParentheses();
		// "()))()())"
		//      ----
		// Ans 4
		task.lengthLongestBParentheses("()))()())");
		// ")()))((()))((()("
		//       ------
		// Ans 6
		task.lengthLongestBParentheses(")()))((()))((()(");
		// ")))((("
		// Ans 0
		task.lengthLongestBParentheses(")))(((");
	}
}

Output

 Given expression : ()))()())
 Length : 4
 Given expression : )()))((()))((()(
 Length : 6
 Given expression : )))(((
 Length : 0
import Foundation;
/*
    Swift 4 program for
    Length of the longest balanced parentheses in a string
*/
struct Stack
{
	private
	var items: [Int] = []
	func peek()->Int
	{
		if (self.isEmpty()==false)
		{
			return items.first!
		}
		else
		{
			fatalError("This stack is empty.")
		}
	}
	func isEmpty()->Bool
	{
		return items.count == 0
	}
	mutating func pop()->Int
	{
		return items.removeFirst()
	}
	mutating func push(_ data: Int)
	{
		items.insert(data, at: 0)
	}
}
class BalancedParentheses
{
	func lengthLongestBParentheses(_ exp: String)
	{
      	var expression = Array(exp);
		var length: Int = 0;
		// Get the length of expression which is contains 
		// open and close parentheses.
		let n: Int = expression.count;
		if (n > 0)
		{
			var record = Stack();
			var count: Int = -1;
			record.push(-1);
			var i: Int = 0;
			while (i < n)
			{
				if (expression[i] == ")")
				{
					// Remove top element
					let _ = record.pop();
					if (record.isEmpty() == false)
					{
						// When record not empty
						count = i - record.peek();
						if (count > length)
						{
							length = count;
						}
					}
					else
					{
						// When stack empty then insert current location
						record.push(i);
					}
				}
				else if (expression[i] == "(")
				{
					// Add current location
					record.push(i);
				}
				else
				{
					// Invalid expression 
					return;
				}
				i += 1;
			}
		}
		// Display given expression
		print(" Given expression : ", exp);
		// Display calculated result
		print(" Length : ", length);
	}
}
func main()
{
	let task: BalancedParentheses = BalancedParentheses();
	// "()))()())"
	//      ----
	// Ans 4
	task.lengthLongestBParentheses("()))()())");
	// ")()))((()))((()("
	//       ------
	// Ans 6
	task.lengthLongestBParentheses(")()))((()))((()(");
	// ")))((("
	// Ans 0
	task.lengthLongestBParentheses(")))(((");
}
main();

Output

 Given expression :  ()))()())
 Length :  4
 Given expression :  )()))((()))((()(
 Length :  6
 Given expression :  )))(((
 Length :  0
import java.util.Stack;
/*
    Kotlin program for
    Length of the longest balanced parentheses in a string
*/
class BalancedParentheses
{
	fun lengthLongestBParentheses(expression: String): Unit
	{
		var length: Int = 0;
		// Get the length of expression which is contains 
		// open and close parentheses.
		val n: Int = expression.length;
		if (n > 0)
		{
			var record: Stack < Int > = Stack < Int > ();
			var count: Int = -1;
			record.push(count);
			var i: Int = 0;
			while (i < n)
			{
				if (expression.get(i) == ')')
				{
					// Remove top element
					record.pop();
					if (record.empty() == false)
					{
						// When record not empty
						count = i - record.peek();
						if (count > length)
						{
							length = count;
						}
					}
					else
					{
						// When stack empty then insert current location
						record.push(i);
					}
				}
				else if (expression.get(i) == '(')
				{
					// Add current location
					record.push(i);
				}
				else
				{
					// Invalid expression 
					return;
				}
				i += 1;
			}
		}
		// Display given expression
		println(" Given expression : " + expression);
		// Display calculated result
		println(" Length : " + length);
	}
}
fun main(args: Array < String > ): Unit
{
	val task: BalancedParentheses = BalancedParentheses();
	// "()))()())"
	//      ----
	// Ans 4
	task.lengthLongestBParentheses("()))()())");
	// ")()))((()))((()("
	//       ------
	// Ans 6
	task.lengthLongestBParentheses(")()))((()))((()(");
	// ")))((("
	// Ans 0
	task.lengthLongestBParentheses(")))(((");
}

Output

 Given expression : ()))()())
 Length : 4
 Given expression : )()))((()))((()(
 Length : 6
 Given expression : )))(((
 Length : 0

Time Complexity

The time complexity of the lengthLongestBParentheses function is O(n), where n is the length of the input expression. This is because we need to iterate through the entire expression once to find the length of the longest balanced parentheses substring.

Output

Based on the provided input, the output of the program will be as follows:

Given expression : ()))()())
Length : 4
Given expression : )()))((()))((()(
Length : 6
Given expression : )))(((
Length : 0

Explanation

  • For the first example "()))()())", the longest balanced parentheses substring is "()" at positions 3 and 4, so the length is 4.
  • For the second example ")()))((()))((()(", the longest balanced parentheses substring is "((()))" at positions 5 to 10, so the length is 6.
  • For the third example ")))(((", there is no balanced parentheses substring, so the length is 0.
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment