Dada una string de paréntesis equilibrada que consta de ‘ ( ‘ y ‘ ) ‘. La tarea es encontrar el número de substrings de paréntesis balanceadas en la string dada
Ejemplos:
Entrada: str = “()()()”
Salida: 6
(),(),(),()(),()(),()()()
Entrada : str = “(())( )”
Salida: 4
(), (()),(), (())()
Enfoque:
supongamos que cada vez que nos encontramos con un paréntesis de apertura, la profundidad aumenta en uno y con un paréntesis de cierre, la profundidad disminuye en uno. Siempre que nos encontremos con el corchete de cierre, aumentemos nuestra respuesta requerida en uno y luego incrementemos nuestra respuesta requerida por las substrings balanceadas ya formadas a esta profundidad.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to find number of
// balanced parentheses sub strings
#include <bits/stdc++.h>
using namespace std;
// Function to find number of
// balanced parentheses sub strings
int Balanced_Substring(string str, int n)
{
// To store required answer
int ans = 0;
// Vector to stores the number of
// balanced brackets at each depth.
vector<int> arr(n / 2 + 1, 0);
// d stores checks the depth of our sequence
// For example level of () is 1
// and that of (()) is 2.
int d = 0;
for (int i = 0; i < n; i++) {
// If open bracket
// increase depth
if (str[i] == '(')
d++;
// If closing bracket
else {
if (d == 1) {
for (int j = 2; j <= n / 2 + 1 && arr[j] != 0; j++)
arr[j] = 0;
}
++ans;
ans += arr[d];
arr[d]++;
d--;
}
}
// Return the required answer
return ans;
}
// Driver code
int main()
{
string str = "()()()";
int n = str.size();
// Function call
cout << Balanced_Substring(str, n);
return 0;
}
Java
// Java program to find number of
// balanced parentheses sub strings
class GFG {
// Function to find number of
// balanced parentheses sub strings
public static int Balanced_Substring(String str,
int n)
{
// To store required answer
int ans = 0;
// Vector to stores the number of
// balanced brackets at each depth.
int[] arr = new int[n / 2 + 1];
// d stores checks the depth of our sequence
// For example level of () is 1
// and that of (()) is 2.
int d = 0;
for (int i = 0; i < n; i++) {
// If open bracket
// increase depth
if (str.charAt(i) == '(')
d++;
// If closing bracket
else {
if (d == 1) {
for (int j = 2; j <= n / 2 + 1 && arr[j] != 0; j++)
arr[j] = 0;
}
++ans;
ans += arr[d];
arr[d]++;
d--;
}
}
// Return the required answer
return ans;
}
// Driver code
public static void main(String[] args)
{
String str = "()()()";
int n = str.length();
// Function call
System.out.println(Balanced_Substring(str, n));
}
}
// This code is contributed by
// sanjeev2552
Python3
# Python3 program to find number of
# balanced parentheses sub strings
# Function to find number of
# balanced parentheses sub strings
def Balanced_Substring(s, n):
# To store required answer
ans = 0;
# Vector to stores the number of
# balanced brackets at each depth.
arr = [0] * (int(n / 2) + 1);
# d stores checks the depth of our sequence
# For example level of () is 1
# and that of (()) is 2.
d = 0;
for i in range(n):
# If open bracket
# increase depth
if (s[i] == '('):
d += 1;
# If closing bracket
else:
if (d == 1):
j = 2
while (j <= n//2 + 1 and arr[j] != 0):
arr[j] = 0
ans += 1;
ans += arr[d];
arr[d] += 1;
d -= 1;
# Return the required answer
return ans;
# Driver code
s = "()()()";
n = len(s);
# Function call
print(Balanced_Substring(s, n));
# This code contributed by Rajput-Ji
C#
// C# program to find number of
// balanced parentheses sub strings
using System;
class GFG {
// Function to find number of
// balanced parentheses sub strings
public static int Balanced_Substring(String str,
int n)
{
// To store required answer
int ans = 0;
// Vector to stores the number of
// balanced brackets at each depth.
int[] arr = new int[n / 2 + 1];
// d stores checks the depth of our sequence
// For example level of () is 1
// and that of (()) is 2.
int d = 0;
for (int i = 0; i < n; i++) {
// If open bracket
// increase depth
if (str[i] == '(')
d++;
// If closing bracket
else {
if (d == 1) {
for (int j = 2; j <= n / 2 + 1 && arr[j] != 0; j++)
arr[j] = 0;
}
++ans;
ans += arr[d];
arr[d]++;
d--;
}
}
// Return the required answer
return ans;
}
// Driver code
public static void Main(String[] args)
{
String str = "()()()";
int n = str.Length;
// Function call
Console.WriteLine(Balanced_Substring(str, n));
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript program to find number of
// balanced parentheses sub strings
// Function to find number of
// balanced parentheses sub strings
function Balanced_Substring(str, n)
{
// To store required answer
let ans = 0;
// Vector to stores the number of
// balanced brackets at each depth.
let arr = new Array(n / 2 + 1).fill(0);
// d stores checks the depth of our sequence
// For example level of () is 1
// and that of (()) is 2.
let d = 0;
for (let i = 0; i < n; i++) {
// If open bracket
// increase depth
if (str[i] == '(')
d++;
// If closing bracket
else {
if (d == 1) {
for (let j = 2; j <= parseInt(n / 2) +
1 && arr[j] != 0; j++)
arr[j] = 0;
}
++ans;
ans += arr[d];
arr[d]++;
d--;
}
}
// Return the required answer
return ans;
}
// Driver code
let str = "()()()";
let n = str.length;
// Function call
document.write(Balanced_Substring(str, n));
</script>
Producción:
6
Complejidad del tiempo : O(N)
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por ShivamKumarsingh1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA