Cuente todos los índices de paréntesis regulares cíclicos

Posted on by Rudeus Greyrat

Dada una string S de longitud N , que consta solo de paréntesis de apertura ‘ ( ‘ y cierre ‘ ) ‘. La tarea es encontrar todos los índices ‘ K ‘ tales que S[K…N-1] + S[0…K-1] sea un paréntesis regular.
 

Una string de paréntesis regulares está vacía («») , «(» + str1 + «)» o str1 + str2 , donde str1 y str2 son strings de paréntesis regulares.
Por ejemplo: “” , “()” , “(())()” y “(()(()))” son strings de paréntesis normales. 
 

Ejemplos: 
 

Entrada: str = «)()(» 
Salida: 2 
Explicación: 
Para K = 1, S =()(), que es regular. 
Para K = 3, S =()(), que es regular.
Entrada: S = “())(” 
Salida: 1 
Explicación: 
Para K = 3, S = (()), que es regular. 
 

Enfoque ingenuo: el enfoque ingenuo consiste en dividir la string dada str en todos los índices posibles (por ejemplo, K ) y comprobar si str[K, N-1] + str[0, K-1] es palindrómico o no. En caso afirmativo, imprima ese valor particular de K .
Complejidad de tiempo: O(N 2 ) 
Espacio auxiliar: O(1)
Enfoque eficiente: La idea es observar que si en cualquier índice (digamos K ) donde el recuento de paréntesis de cierre es mayor que el recuento de paréntesis de apertura, entonces ese índice es el posible índice de dividir la string. A continuación se muestran los pasos: 
 

  1. La partición sólo es posible cuando el número de paréntesis de apertura debe ser igual al número de paréntesis de cierre. De lo contrario, no podemos formar ninguna partición para equilibrar el paréntesis.
  2. Cree una array auxiliar (por ejemplo , aux[] ) del tamaño de la string.
  3. Recorra la string dada si el carácter en cualquier índice (por ejemplo, i ) es ‘(‘, luego actualice aux[i] a 1; de lo contrario, actualice strong>aux[i] a -1.
  4. La frecuencia del elemento mínimo en la array auxiliar anterior es el número requerido de división (digamos en el índice K ) para hacer que S[K…N-1] + S[0…K-1] sea una string de paréntesis regular.

A continuación se muestra la implementación del enfoque anterior:
 

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find all indices which
// cyclic shift leads to get
// balanced parenthesis
int countCyclicShifts(string& S, int n)
{
    int aux[n] = { 0 };
 
    // Create auxiliary array
    for (int i = 0; i < n; ++i) {
        if (S[i] == '(')
            aux[i] = 1;
        else
            aux[i] = -1;
    }
 
    // Finding prefix sum and
    // minimum element
    int mn = aux[0];
 
    for (int i = 1; i < n; ++i) {
        aux[i] += aux[i - 1];
 
        // Update the minimum element
        mn = min(mn, aux[i]);
    }
 
    // ChecK if count of '(' and
    // ')' are equal
    if (aux[n - 1] != 0)
        return 0;
 
    // Find count of minimum
    // element
    int count = 0;
 
    // Find the frequency of mn
    for (int i = 0; i < n; ++i) {
        if (aux[i] == mn)
            count++;
    }
 
    // Return the count
    return count;
}
 
// Driver Code
int main()
{
    // Given string S
    string S = ")()(";
 
    int N = S.length();
 
    // Function Call
    cout << countCyclicShifts(S, N);
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
     
// Function to find all indices which
// cyclic shift leads to get
// balanced parenthesis
static int countCyclicShifts(String S, int n)
{
     
    // Create auxiliary array
    int[] aux = new int[n];
     
    for(int i = 0; i < n; ++i)
    {
       if (S.charAt(i) == '(')
           aux[i] = 1;
       else
           aux[i] = -1;
    }
     
    // Finding prefix sum and
    // minimum element
    int mn = aux[0];
     
    for(int i = 1; i < n; ++i)
    {
       aux[i] += aux[i - 1];
        
       // Update the minimum element
       mn = Math.min(mn, aux[i]);
    }
     
    // Check if count of '(' and ')'
    // are equal
    if (aux[n - 1] != 0)
        return 0;
     
    // Find count of minimum
    // element
    int count = 0;
     
    // Find the frequency of mn
    for(int i = 0; i < n; ++i)
    {
       if (aux[i] == mn)
           count++;
    }
     
    // Return the count
    return count;
}
 
// Driver code
public static void main(String[] args)
{
     
    // Given string S
    String S = ")()(";
         
    // length of the string S
    int N = S.length();
         
    System.out.print(countCyclicShifts(S, N));
}
}
 
// This code is contributed by sanjoy_62

Python3

# Python3 program for the above approach
 
# Function to find all indices which
# cyclic shift leads to get
# balanced parenthesis
def countCyclicShifts(S, n):
     
    aux = [0 for i in range(n)]
 
    # Create auxiliary array
    for i in range(0, n):
        if (S[i] == '('):
            aux[i] = 1
        else:
            aux[i] = -1
 
    # Finding prefix sum and
    # minimum element
    mn = aux[0]
 
    for i in range(1, n):
        aux[i] += aux[i - 1]
 
        # Update the minimum element
        mn = min(mn, aux[i])
 
    # ChecK if count of '(' and
    # ')' are equal
    if (aux[n - 1] != 0):
        return 0
 
    # Find count of minimum
    # element
    count = 0
 
    # Find the frequency of mn
    for i in range(0, n):
        if (aux[i] == mn):
            count += 1
 
    # Return the count
    return count
 
# Driver Code
 
# Given string S
S = ")()("
N = len(S)
 
# Function call
print(countCyclicShifts(S, N))
 
# This code is contributed by Sanjit_Prasad

C#

// C# program for the above approach
using System;
 
class GFG{
     
// Function to find all indices which
// cyclic shift leads to get
// balanced parenthesis
static int countCyclicShifts(string S, int n)
{
     
    // Create auxiliary array
    int[] aux = new int[n];
     
    for(int i = 0; i < n; ++i)
    {
        if (S[i] == '(')
            aux[i] = 1;
        else
            aux[i] = -1;
    }
     
    // Finding prefix sum and
    // minimum element
    int mn = aux[0];
     
    for(int i = 1; i < n; ++i)
    {
        aux[i] += aux[i - 1];
             
        // Update the minimum element
        mn = Math.Min(mn, aux[i]);
    }
     
    // Check if count of '(' and ')'
    // are equal
    if (aux[n - 1] != 0)
        return 0;
     
    // Find count of minimum
    // element
    int count = 0;
     
    // Find the frequency of mn
    for(int i = 0; i < n; ++i)
    {
        if (aux[i] == mn)
            count++;
    }
     
    // Return the count
    return count;
}
 
// Driver code
public static void Main(string[] args)
{
     
    // Given string S
    string S = ")()(";
         
    // length of the string S
    int N = S.Length;
         
    Console.Write(countCyclicShifts(S, N));
}
}
 
// This code is contributed by rutvik_56

Javascript

<script>
// Javascript Program to implement
// the above approach
 
// Function to find all indices which
// cyclic shift leads to get
// balanced parenthesis
function countCyclicShifts(S, n)
{
       
    // Create auxiliary array
    let aux = [];
       
    for(let i = 0; i < n; ++i)
    {
       if (S[i] == '(')
           aux[i] = 1;
       else
           aux[i] = -1;
    }
       
    // Finding prefix sum and
    // minimum element
    let mn = aux[0];
       
    for(let i = 1; i < n; ++i)
    {
       aux[i] += aux[i - 1];
          
       // Update the minimum element
       mn = Math.min(mn, aux[i]);
    }
       
    // Check if count of '(' and ')'
    // are equal
    if (aux[n - 1] != 0)
        return 0;
       
    // Find count of minimum
    // element
    let count = 0;
       
    // Find the frequency of mn
    for(let i = 0; i < n; ++i)
    {
       if (aux[i] == mn)
           count++;
    }
       
    // Return the count
    return count;
}
 
// Driver Code
     
    // Given string S
    let S = ")()(";
           
    // length of the string S
    let N = S.length;
           
    document.write(countCyclicShifts(S, N));   
 
// This code is contributed by avijitmondal1998.
</script>
Producción:

2

Complejidad de tiempo: O(N) , donde N es la longitud de la string. 
Espacio auxiliar: O(N) , donde N es la longitud de la string.

Publicación traducida automáticamente

Artículo escrito por Sanjit_Prasad y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *