Dada una string de corchetes abiertos ‘(‘ y corchetes cerrados ‘)’. La tarea es encontrar la longitud del prefijo balanceado más largo.
Ejemplos:
C++
// CPP Program to find length of longest balanced // parentheses prefix. #include <bits/stdc++.h> using namespace std; // Return the length of longest balanced parentheses // prefix. int maxbalancedprefix(char str[], int n) { int sum = 0; int maxi = 0; // Traversing the string. for (int i = 0; i < n; i++) { // If open bracket add 1 to sum. if (str[i] == '(') sum += 1; // If closed bracket subtract 1 // from sum else sum -= 1; // if first bracket is closing bracket // then this condition would help if (sum < 0) break; // If sum is 0, store the index // value. if (sum == 0) maxi = i + 1; } return maxi; } // Driven Program int main() { char str[] = "((()())())(("; int n = strlen(str); cout << maxbalancedprefix(str, n) << endl; return 0; }
Java
// Java Program to find length of longest // balanced parentheses prefix. import java.io.*; class GFG { // Return the length of longest // balanced parentheses prefix. static int maxbalancedprefix(String str, int n) { int sum = 0; int maxi = 0; // Traversing the string. for (int i = 0; i < n; i++) { // If open bracket add 1 to sum. if (str.charAt(i) == '(') sum += 1; // If closed bracket subtract 1 // from sum else sum -= 1; // if first bracket is closing bracket // then this condition would help if (sum < 0) break; // If sum is 0, store the index // value. if (sum == 0) maxi = i + 1; } return maxi; } // Driven Program public static void main(String[] args) { String str = "((()())())(("; int n = str.length(); System.out.println(maxbalancedprefix(str, n)); } } // This code is contributed by vt_m
Python3
# Python3 code to find length of # longest balanced parentheses prefix. # Function to return the length of # longest balanced parentheses prefix. def maxbalancedprefix (str, n): _sum = 0 maxi = 0 # Traversing the string. for i in range(n): # If open bracket add 1 to sum. if str[i] == '(': _sum += 1 # If closed bracket subtract 1 # from sum else: _sum -= 1 # if first bracket is closing bracket # then this condition would help if _sum < 0: break # If sum is 0, store the # index value. if _sum == 0: maxi = i + 1 return maxi # Driver Code str = '((()())())((' n = len(str) print(maxbalancedprefix (str, n)) # This code is contributed by "Abhishek Sharma 44"
C#
// C# Program to find length of longest // balanced parentheses prefix. using System; class GFG { // Return the length of longest // balanced parentheses prefix. static int maxbalancedprefix(string str, int n) { int sum = 0; int maxi = 0; // Traversing the string. for (int i = 0; i < n; i++) { // If open bracket add 1 to sum. if (str[i] == '(') sum += 1; // If closed bracket subtract 1 // from sum else sum -= 1; // if first bracket is closing bracket // then this condition would help if (sum < 0) break; // If sum is 0, store the index // value. if (sum == 0) maxi = i + 1; } return maxi; } // Driven Program public static void Main() { string str = "((()())())(("; int n = str.Length; Console.WriteLine(maxbalancedprefix(str, n)); } } // This code is contributed by vt_m
PHP
<?php // PHP Program to find length // of longest balanced // parentheses prefix. // Return the length of longest // balanced parentheses prefix. function maxbalancedprefix($str, $n) { $sum = 0; $maxi = 0; // Traversing the string. for ($i = 0; $i <$n; $i++) { // If open bracket add 1 to sum. if ($str[$i] == '(') $sum += 1; // If closed bracket subtract 1 // from sum else $sum -= 1; if ($sum < 0) break; // If sum is 0, store the index // value. if ($sum == 0) $maxi = $i+1; } return $maxi; } // Driver Code $str = array('(', '(', '(', ')', '(', ')', ')', '(', ')', ')', '(', '('); $n = count($str); echo maxbalancedprefix($str, $n); // This code is contributed by anuj_67.. ?>
Javascript
<script> // Javascript Program to find // length of longest balanced // parentheses prefix. // Return the length of longest // balanced parentheses // prefix. function maxbalancedprefix( str, n) { var sum = 0; var maxi = 0; // Traversing the string. for (var i = 0; i < n; i++) { // If open bracket add 1 to sum. if (str[i] == '(') sum += 1; // If closed bracket subtract 1 // from sum else sum -= 1; // if first bracket is closing bracket // then this condition would help if (sum < 0) break; // If sum is 0, store the index // value. if (sum == 0) maxi = i + 1; } return maxi; } // Driven Program var str = "((()())())(("; var n = str.length; document.write( maxbalancedprefix(str, n)); </script>