Dadas N secuencias de corchetes, la tarea es encontrar el número de pares de secuencias de corchetes mediante la unión de los cuales se puede obtener una secuencia de corchetes equilibrada como un todo. Una secuencia de corchetes entre paréntesis solo puede ser parte de un solo par.
Ejemplos:
Input: { ")())", ")", "((", "((", "(", ")", ")"}
Output: 2
Bracket sequence {1, 3} and {5, 6}
Input: {"()", "(())", "(())", "()"}
Output: 2
Since all brackets are balanced, hence we can form 2 pairs with 4.
Enfoque: Se pueden seguir los siguientes pasos para resolver el problema anterior:
- Cuente los corchetes de apertura y cierre requeridos, de individuos.
- Si los paréntesis de cierre requeridos son > 0 y los paréntesis de apertura son 0, entonces haga un hash del número de cierre requerido del paréntesis.
- De manera similar, si los paréntesis de apertura requeridos son > 0 y los corchetes de cierre son 0, entonces haga un hash del número de apertura requerido del paréntesis.
- Cuente las secuencias de paréntesis equilibrados.
- Agregue (número de secuencias de paréntesis equilibradas/2) al número de pares.
- Por cada número de secuencias que requiera el mismo número de paréntesis de apertura, min(hash[abrir], hash[cerrar]) se agregará al número de pares
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to count the number of pairs
// of balanced parentheses
#include <bits/stdc++.h>
using namespace std;
// Function to count the number of pairs
int countPairs(string bracks[], int num)
{
// Hashing function to count the
// opening and closing brackets
unordered_map<int, int> open, close;
int cnt = 0;
// Traverse for all bracket sequences
for (int i = 0; i < num; i++) {
// Get the string
string s = bracks[i];
int l = s.length();
// Counts the opening and closing required
int op = 0, cl = 0;
// Traverse in the string
for (int j = 0; j < l; j++) {
// If it is a opening bracket
if (s[j] == '(')
op++;
else // Closing bracket
{
// If openings are there, then close it
if (op)
op--;
else // Else increase count of closing
cl++;
}
}
// If requirements of openings
// are there and no closing
if (op && !cl)
open[op]++;
// If requirements of closing
// are there and no opening
if (cl && !op)
close[cl]++;
// Perfect
if (!op && !cl)
cnt++;
}
// Divide by two since two
// perfect makes one pair
cnt = cnt / 2;
// Traverse in the open and find
// corresponding minimum
for (auto it : open)
cnt += min(it.second, close[it.first]);
return cnt;
}
// Driver Code
int main()
{
string bracks[] = { ")())", ")", "((", "((", "(", ")", ")" };
int num = sizeof(bracks) / sizeof(bracks[0]);
cout << countPairs(bracks, num);
}
Java
// Java program to count the number of pairs
// of balanced parentheses
import java.util.HashMap;
class GFG
{
// Function to count the number of pairs
static int countPairs(String[] bracks, int num)
{
// Hashing function to count the
// opening and closing brackets
HashMap<Integer, Integer> open = new HashMap<>();
HashMap<Integer, Integer> close = new HashMap<>();
int cnt = 0;
// Traverse for all bracket sequences
for (int i = 0; i < num; i++)
{
// Get the string
String s = bracks[i];
int l = s.length();
// Counts the opening and closing required
int op = 0, cl = 0;
// Traverse in the string
for (int j = 0; j < l; j++)
{
// If it is a opening bracket
if (s.charAt(j) == '(')
op++;
// Closing bracket
else
{
// If openings are there, then close it
if (op != 0)
op--;
// Else increase count of closing
else
cl++;
}
}
// If requirements of openings
// are there and no closing
if (op != 0 && cl == 0)
open.put(op, open.get(op) == null ?
1 : open.get(op) + 1);
// If requirements of closing
// are there and no opening
if (cl != 0 && op == 0)
close.put(cl, close.get(cl) == null ?
1 : close.get(cl) + 1);
// Perfect
if (op == 0 && cl == 0)
cnt++;
}
// Divide by two since two
// perfect makes one pair
cnt /= 2;
// Traverse in the open and find
// corresponding minimum
for (HashMap.Entry<Integer,
Integer> it : open.entrySet())
cnt += Math.min(it.getValue(),
close.get(it.getKey()));
return cnt;
}
// Driver Code
public static void main(String[] args)
{
String[] bracks = { ")())", ")", "((",
"((", "(", ")", ")" };
int num = bracks.length;
System.out.println(countPairs(bracks, num));
}
}
// This code is contributed by
// sanjeev2552
Python3
# Python3 program to count the number of pairs
# of balanced parentheses
import math as mt
# Function to count the number of pairs
def countPairs(bracks, num):
# Hashing function to count the
# opening and closing brackets
openn=dict()
close=dict()
cnt = 0
# Traverse for all bracket sequences
for i in range(num):
# Get the string
s = bracks[i]
l = len(s)
# Counts the opening and closing required
op,cl = 0,0
# Traverse in the string
for j in range(l):
# If it is a opening bracket
if (s[j] == '('):
op+=1
else: # Closing bracket
# If openings are there, then close it
if (op):
op-=1
else: # Else increase count of closing
cl+=1
# If requirements of openings
# are there and no closing
if (op and cl==0):
if op in openn.keys():
openn[op]+=1
else:
openn[op]=1
# If requirements of closing
# are there and no opening
if (cl and op==0):
if cl in openn.keys():
close[cl]+=1
else:
close[cl]=1
# Perfect
if (op==0 and cl==0):
cnt+=1
# Divide by two since two
# perfect makes one pair
cnt = cnt //2
# Traverse in the open and find
# corresponding minimum
for it in openn:
cnt += min(openn[it], close[it])
return cnt
# Driver Code
bracks= [")())", ")", "((", "((", "(", ")", ")" ]
num = len(bracks)
print(countPairs(bracks, num))
#This code is contributed by Mohit kumar 29
C#
// C# program to count the number of pairs
// of balanced parentheses
using System;
using System.Collections.Generic;
class GFG{
// Function to count the number of pairs
static int countPairs(string[] bracks, int num)
{
// Hashing function to count the
// opening and closing brackets
Dictionary<int,
int> open = new Dictionary<int,
int>();
Dictionary<int,
int> close = new Dictionary<int,
int>();
int cnt = 0;
// Traverse for all bracket sequences
for(int i = 0; i < num; i++)
{
// Get the string
string s = bracks[i];
int l = s.Length;
// Counts the opening and closing required
int op = 0, cl = 0;
// Traverse in the string
for(int j = 0; j < l; j++)
{
// If it is a opening bracket
if (s[j] == '(')
op++;
// Closing bracket
else
{
// If openings are there, then close it
if (op != 0)
op--;
// Else increase count of closing
else
cl++;
}
}
// If requirements of openings
// are there and no closing
if (op != 0 && cl == 0)
{
if (open.ContainsKey(op))
{
open[op]++;
}
else
{
open[op] = 1;
}
}
// If requirements of closing
// are there and no opening
if (cl != 0 && op == 0)
{
if (close.ContainsKey(cl))
{
close[cl]++;
}
else
{
close[cl] = 1;
}
}
// Perfect
if (op == 0 && cl == 0)
cnt++;
}
// Divide by two since two
// perfect makes one pair
cnt /= 2;
// Traverse in the open and find
// corresponding minimum
foreach(KeyValuePair<int, int> it in open)
{
cnt += Math.Min(it.Value, close[it.Value]);
}
return cnt;
}
// Driver Code
public static void Main(string[] args)
{
string[] bracks = { ")())", ")", "((",
"((", "(", ")", ")" };
int num = bracks.Length;
Console.Write(countPairs(bracks, num));
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// Javascript program to count the number of pairs
// of balanced parentheses
// Function to count the number of pairs
function countPairs( bracks,num)
{
// Hashing function to count the
// opening and closing brackets
let open = new Map();
let close = new Map();
let cnt = 0;
// Traverse for all bracket sequences
for (let i = 0; i < num; i++)
{
// Get the string
let s = bracks[i];
let l = s.length;
// Counts the opening and closing required
let op = 0, cl = 0;
// Traverse in the string
for (let j = 0; j < l; j++)
{
// If it is a opening bracket
if (s[j] == '(')
op++;
// Closing bracket
else
{
// If openings are there, then close it
if (op != 0)
op--;
// Else increase count of closing
else
cl++;
}
}
// If requirements of openings
// are there and no closing
if (op != 0 && cl == 0)
open.set(op, open.get(op) == null ?
1 : open.get(op) + 1);
// If requirements of closing
// are there and no opening
if (cl != 0 && op == 0)
close.set(cl, close.get(cl) == null ?
1 : close.get(cl) + 1);
// Perfect
if (op == 0 && cl == 0)
cnt++;
}
// Divide by two since two
// perfect makes one pair
cnt /= 2;
// Traverse in the open and find
// corresponding minimum
for (let [key, value] of open.entries())
cnt += Math.min(value,
close.get(value));
return cnt;
}
// Driver Code
let bracks=[")())", ")", "((",
"((", "(", ")", ")"];
let num = bracks.length;
document.write(countPairs(bracks, num));
// This code is contributed by patel2127
</script>
Producción:
2
Complejidad de tiempo: O(N*M), ya que estamos usando bucles anidados para atravesar N*M veces. Donde N es el número de strings en los corchetes y M es la longitud máxima de las strings presentes en los corchetes.
Espacio auxiliar: O(N), ya que estamos usando espacio extra para el mapa. Donde N es el número de strings entre corchetes.