Length of longest balanced parentheses prefix
Last Updated :
22 Jul, 2024
Given a string of open bracket ‘(‘ and closed bracket ‘)’. The task is to find the length of longest balanced prefix.
Examples:
Input : S = "((()())())(("
Output : 10
From index 0 to index 9, they are forming
a balanced parentheses prefix.
Input : S = "()(())((()"
Output : 6
The idea is take value of open bracket ‘(‘ as 1 and value of close bracket ‘)’ as -1. Now start finding the prefix sum of the given string. The farthest index, say maxi, where the value of sum is 0 is the index upto which longest balanced prefix exists. So the answer would be maxi + 1.
Below is the implementation of this approach:
C++
#include <iostream>
#include <string>
using namespace std;
// Return the length of the longest balanced parentheses
// prefix.
int maxbalancedprefix(string str, int n)
{
int sum = 0;
int max_length = 0;
int open_count = 0;
// Traversing the string.
for (int i = 0; i < n; i++) {
// If open bracket, increment open_count.
if (str[i] == '(') {
sum += 1;
open_count++;
}
// If closed bracket, decrement sum.
else {
sum -= 1;
if (open_count > 0) {
open_count--;
max_length
= i + 1; // Update max_length to current
// index if valid prefix found.
}
else {
break; // Break if closed bracket
// encountered before open bracket.
}
}
}
return max_length;
}
int main()
{
string str = "(()))())";
int n = str.length();
cout << maxbalancedprefix(str, n) << endl; // Output: 10
return 0;
}
import java.io.*;
class GFG {
// Return the length of the longest balanced parentheses
// prefix.
static int maxbalancedprefix(String str, int n)
{
int sum = 0;
int max_length = 0;
int open_count = 0;
// Traversing the string.
for (int i = 0; i < n; i++) {
// If open bracket, increment open_count.
if (str.charAt(i) == '(') {
sum += 1;
open_count++;
}
// If closed bracket, decrement sum.
else {
sum -= 1;
if (open_count > 0) {
open_count--;
max_length
= i + 1; // Update max_length to
// current index if valid
// prefix found.
}
else {
break; // Break if closed bracket
// encountered before open
// bracket.
}
}
}
return max_length;
}
// Driven Program
public static void main(String[] args)
{
String str = "((()())())((";
int n = str.length();
System.out.println(
maxbalancedprefix(str, n)); // Output: 10
}
}
def maxbalancedprefix(s):
sum = 0
max_length = 0
open_count = 0
# Traversing the string.
for i in range(len(s)):
# If open bracket, increment open_count.
if s[i] == '(':
sum += 1
open_count += 1
# If closed bracket, decrement sum.
else:
sum -= 1
if open_count > 0:
open_count -= 1
# Update max_length to current index if valid prefix found.
max_length = i + 1
else:
# Break if closed bracket encountered before open bracket.
break
return max_length
# Test the function with the provided input
s = "((()())())(("
print(maxbalancedprefix(s)) # Output: 10
using System;
class Program {
// Return the length of the longest balanced parentheses
// prefix.
static int MaxBalancedPrefix(string str)
{
int sum = 0;
int max_length = 0;
int open_count = 0;
// Traversing the string.
for (int i = 0; i < str.Length; i++) {
// If open bracket, increment open_count.
if (str[i] == '(') {
sum += 1;
open_count++;
}
// If closed bracket, decrement sum.
else {
sum -= 1;
if (open_count > 0) {
open_count--;
max_length
= i + 1; // Update max_length to
// current index if valid
// prefix found.
}
else {
break; // Break if closed bracket
// encountered before open
// bracket.
}
}
}
return max_length;
}
static void Main(string[] args)
{
string str = "((()())())((";
Console.WriteLine(
MaxBalancedPrefix(str)); // Output: 10
}
}
// Return the length of the longest balanced parentheses prefix.
function maxbalancedprefix(str) {
let sum = 0;
let max_length = 0;
let open_count = 0;
// Traversing the string.
for (let i = 0; i < str.length; i++) {
// If open bracket, increment open_count.
if (str[i] === '(') {
sum += 1;
open_count++;
}
// If closed bracket, decrement sum.
else {
sum -= 1;
if (open_count > 0) {
open_count--;
max_length = i + 1; // Update max_length to current index if valid prefix found.
} else {
break; // Break if closed bracket encountered before open bracket.
}
}
}
return max_length;
}
let str = "((()())())((";
console.log(maxbalancedprefix(str)); // Output: 10
<?php
// Return the length of the longest balanced parentheses prefix.
function maxbalancedprefix($str) {
$max_length = 0;
$open_count = 0;
// Traversing the string.
for ($i = 0; $i < strlen($str); $i++) {
// If open bracket, increment open_count and continue.
if ($str[$i] == '(') {
$open_count++;
}
// If closed bracket, decrement open_count.
else {
$open_count--;
// Update max_length if valid prefix found.
if ($open_count >= 0) {
$max_length = $i + 1; // Update max_length to current index if valid prefix found.
} else {
break; // Break if closed bracket encountered before open bracket.
}
}
}
return $max_length;
}
// Test the function with the provided input
$str = "((()())())((";
echo maxbalancedprefix($str); // Output: 10
?>
Time complexity: O(length(str))
Auxiliary space: O(1)
Another Approach:
Initialize two variables, balance and max_len, to zero.
Traverse the string from left to right:
a. If the current character is ‘(‘, increment the balance variable, else decrement it.
b. If the balance variable is negative, reset it to zero and move the max_len pointer to the right.
c. If the balance variable is zero, update the max_len if the current substring length is greater than max_len.
Return max_len.
C++
#include <iostream>
#include <string>
using namespace std;
// Return the length of the longest balanced parentheses prefix.
int maxbalancedprefix(string str) {
int balance = 0;
int max_len = 0;
for (int i = 0; i < str.length(); i++) {
if (str[i] == '(') {
balance++;
} else {
balance--;
}
if (balance < 0) {
break;
} else if (balance == 0) {
max_len = i + 1 > max_len ? i + 1 : max_len;
}
}
return max_len;
}
int main() {
string str = "(()))())";
cout << "Length of longest balanced parentheses prefix is: " << maxbalancedprefix(str) << endl; // Output: 4
return 0;
}
#include <stdio.h>
#include <string.h>
// Return the length of the longest balanced parentheses
// prefix.
int maxbalancedprefix(char* str)
{
int balance = 0;
int max_len = 0;
for (int i = 0; i < strlen(str); i++) {
if (str[i] == '(') {
balance++;
}
else {
balance--;
}
if (balance < 0) {
break;
}
else if (balance == 0) {
max_len = i + 1 > max_len ? i + 1 : max_len;
}
}
return max_len;
}
int main()
{
char str[] = "(()))())";
printf("Length of longest balanced parentheses prefix "
"is: %d\n",
maxbalancedprefix(str)); // Output: 4
return 0;
}
import java.util.*;
public class Main {
public static void main(String[] args)
{
String str = "(()))())";
int n = str.length();
int balance = 0;
int max_len = 0;
for (int i = 0; i < n; i++) {
if (str.charAt(i) == '(') {
balance++;
}
else {
balance--;
}
if (balance < 0) {
break;
}
else if (balance == 0) {
max_len = i + 1 > max_len ? i + 1 : max_len;
}
}
System.out.println(
"Length of longest balanced parentheses prefix is: "
+ max_len);
}
}
def maxbalancedprefix(s):
balance = 0
max_len = 0
for i in range(len(s)):
if s[i] == '(':
balance += 1
else:
balance -= 1
if balance < 0:
break
elif balance == 0:
max_len = i + 1 if i + 1 > max_len else max_len
return max_len
# Test the function with the provided input
s = "(()))())"
print("Length of longest balanced parentheses prefix is:",
maxbalancedprefix(s)) # Output: 4
using System;
class Program {
// Return the length of the longest balanced parentheses
// prefix.
static int MaxBalancedPrefix(string str)
{
int balance = 0;
int max_len = 0;
for (int i = 0; i < str.Length; i++) {
if (str[i] == '(') {
balance++;
}
else {
balance--;
}
if (balance < 0) {
break;
}
else if (balance == 0) {
max_len = i + 1 > max_len ? i + 1 : max_len;
}
}
return max_len;
}
static void Main(string[] args)
{
string str = "(()))())";
Console.WriteLine(
"Length of longest balanced parentheses prefix is: "
+ MaxBalancedPrefix(str)); // Output: 4
}
}
// Return the length of the longest balanced parentheses prefix.
function maxbalancedprefix(str) {
let balance = 0;
let max_len = 0;
for (let i = 0; i < str.length; i++) {
if (str[i] === '(') {
balance++;
} else {
balance--;
}
if (balance < 0) {
break;
} else if (balance === 0) {
max_len = i + 1 > max_len ? i + 1 : max_len;
}
}
return max_len;
}
let str = "(()))())";
console.log("Length of longest balanced parentheses prefix is:", maxbalancedprefix(str)); // Output: 4
<?php
// Return the length of the longest balanced parentheses prefix.
function maxbalancedprefix($str) {
$n = strlen($str); // Store the length of $str
$balance = 0;
$max_len = 0;
for ($i = 0; $i < $n; $i++) {
if ($str[$i] == '(') {
$balance++;
} else {
$balance--;
}
if ($balance < 0) {
break;
} else if ($balance == 0) {
$max_len = $i + 1; // Update max_len directly without comparison
}
}
return $max_len;
}
// Test the function with the provided input
$str = "(()))())";
echo "Length of longest balanced parentheses prefix is: " . maxbalancedprefix($str); // Output: 4
?>
OutputLength of longest balanced parentheses prefix is: 4
time complexity of O(n), where n is the length of the string
space complexity of O(1)
Similar Reads
Mastering Bracket Problems for Competitive Programming
Bracket problems in programming typically refer to problems that involve working with parentheses, and/or braces in expressions or sequences. It typically refers to problems related to the correct and balanced usage of parentheses, and braces in expressions or code. These problems often involve chec
4 min read
Check if given Parentheses expression is balanced or not
Given a string str of length N, consisting of '(' and ')' only, the task is to check whether it is balanced or not.Examples: Input: str = "((()))()()" Output: BalancedInput: str = "())((())" Output: Not Balanced Approach 1: Declare a Flag variable which denotes expression is balanced or not.Initiali
9 min read
Valid Parentheses in an Expression
Given a string s representing an expression containing various types of brackets: {}, (), and [], the task is to determine whether the brackets in the expression are balanced or not. A balanced expression is one where every opening bracket has a corresponding closing bracket in the correct order. Ex
8 min read
Length of longest balanced parentheses prefix
Given a string of open bracket '(' and closed bracket ')'. The task is to find the length of longest balanced prefix. Examples: Input : S = "((()())())((" Output : 10From index 0 to index 9, they are forming a balanced parentheses prefix.Input : S = "()(())((()"Output : 6 The idea is take value of o
9 min read
Modify a numeric string to a balanced parentheses by replacements
Given a numeric string S made up of characters '1', '2' and '3' only, the task is to replace characters with either an open bracket ( '(' ) or a closed bracket ( ')' ) such that the newly formed string becomes a balanced bracket sequence. Note: All occurrences of a character must be replaced by the
10 min read
Check if the bracket sequence can be balanced with at most one change in the position of a bracket
Given an unbalanced bracket sequence as a string str, the task is to find whether the given string can be balanced by moving at most one bracket from its original place in the sequence to any other position.Examples: Input: str = ")(()" Output: Yes As by moving s[0] to the end will make it valid. "(
6 min read
Number of closing brackets needed to complete a regular bracket sequence
Given an incomplete bracket sequence S. The task is to find the number of closing brackets ')' needed to make it a regular bracket sequence and print the complete bracket sequence. You are allowed to add the brackets only at the end of the given bracket sequence. If it is not possible to complete th
7 min read
Minimum number of Parentheses to be added to make it valid
Given a string S of parentheses '(' or ')' where, [Tex]0\leq len(S)\leq 1000 [/Tex]. The task is to find a minimum number of parentheses '(' or ')' (at any positions) we must add to make the resulting parentheses string is valid. Examples: Input: str = "())" Output: 1 One '(' is required at beginnin
9 min read
Minimum bracket reversals to make an expression balanced
Given an expression with only '}' and '{'. The expression may not be balanced. Find minimum number of bracket reversals to make the expression balanced. Examples: Input: s = "}{{}}{{{"Output: 3Explanation: We need to reverse minimum 3 brackets to make "{{{}}{}}". Input: s = "{{"Output: 1Explanation:
15+ min read
Find the number of valid parentheses expressions of given length
Given a number n, the task is to find the number of valid parentheses expressions of that length. Examples : Input: 2Output: 1 Explanation: There is only possible valid expression of length 2, "()"Input: 4Output: 2 Explanation: Possible valid expression of length 4 are "(())" and "()()" Input: 6Outp
11 min read