# 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) == '(')
{
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)
{
// "()))()())"
//      ----
// Ans 4
// ")()))((()))((()("
//       ------
// Ans 6
// ")))((("
// Ans 0
}
}``````

#### 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] == '(')
{
record.push(i);
}
else
{
// Invalid expression
return;
}
}
}
// Display given expression
cout << " Given expression : " << expression << endl;
// Display calculated result
cout << " Length : " << length << endl;
}
};
int main()
{
// "()))()())"
//      ----
// Ans 4
// ")()))((()))((()("
//       ------
// Ans 6
// ")))((("
// Ans 0
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] == '(')
{
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)
{
// "()))()())"
//      ----
// Ans 4
// ")()))((()))((()("
//       ------
// Ans 6
// ")))((("
// Ans 0
}
}``````

#### 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] == '(' {
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] == '(')
{
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()
{
// "()))()())"
//      ----
// Ans 4
// ")()))((()))((()("
//       ------
// Ans 6
// ")))((("
// Ans 0
}
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) == '(')
{
record.push(i);
}
else
{
// Invalid expression
return;
}
}
}
// Display given expression
console.log(" Given expression : " + expression);
// Display calculated result
console.log(" Length : " + length);
}
}

function main()
{
// "()))()())"
//      ----
// Ans 4
// ")()))((()))((()("
//       ------
// Ans 6
// ")))((("
// Ans 0
}
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] == '(') :
record.append(i)
else :
#  Invalid expression
return

i += 1

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

def main() :
#  "()))()())"
#       ----
#  Ans 4
#  ")()))((()))((()("
#        ------
#  Ans 6
#  ")))((("
#  Ans 0

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] == '(')
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()
#  "()))()())"
#       ----
#  Ans 4
#  ")()))((()))((()("
#        ------
#  Ans 6
#  ")))((("
#  Ans 0
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) == '(')
{
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
// ")()))((()))((()("
//       ------
// Ans 6
// ")))((("
// Ans 0
}
}``````

#### 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] == "(")
{
record.push(i);
}
else
{
// Invalid expression
return;
}
i += 1;
}
}
// Display given expression
print(" Given expression : ", exp);
// Display calculated result
print(" Length : ", length);
}
}
func main()
{
// "()))()())"
//      ----
// Ans 4
// ")()))((()))((()("
//       ------
// Ans 6
// ")))((("
// Ans 0
}
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) == '(')
{
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
{
// "()))()())"
//      ----
// Ans 4
// ")()))((()))((()("
//       ------
// Ans 6
// ")))((("
// Ans 0
}``````

#### 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.

## 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.