Dada una string str de longitud N , la tarea es encontrar el número de formas de insertar solo 2 pares de paréntesis en la string dada de modo que la string resultante siga siendo válida.
Ejemplos:
Entrada: str = “ab”
Salida: 6
((a))b, ((a)b), ((ab)), (a)(b), (a(b)), a((b))
que son un total de 6 vías.
Entrada: str = “aab”
Salida: 20
Planteamiento: se puede observar que para las longitudes de la cuerda 1, 2, 3,…, N se formará una serie como 1, 6, 20, 50, 105, 196, 336, 540,… cuyo N -ésimo término es (N + 1) 2 * ((N + 1) 2 – 1) / 12 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the number of ways // to insert the bracket pairs int cntWays(string str, int n) { int x = n + 1; int ways = x * x * (x * x - 1) / 12; return ways; } // Driver code int main() { string str = "ab"; int n = str.length(); cout << cntWays(str, n); return 0; }
Java
// Java implementation of the approach import java.util.*; class GFG { // Function to return the number of ways // to insert the bracket pairs static int cntWays(String str, int n) { int x = n + 1; int ways = x * x * (x * x - 1) / 12; return ways; } // Driver code public static void main(String []args) { String str = "ab"; int n = str.length(); System.out.println(cntWays(str, n)); } } // This code is contributed by Rajput-Ji
Python3
# Python3 implementation of the approach # Function to return the number of ways # to insert the bracket pairs def cntWays(string, n) : x = n + 1; ways = x * x * (x * x - 1) // 12; return ways; # Driver code if __name__ == "__main__" : string = "ab"; n = len(string); print(cntWays(string, n)); # This code is contributed by AnkitRai01
C#
// C# implementation of the approach using System; class GFG { // Function to return the number of ways // to insert the bracket pairs static int cntWays(String str, int n) { int x = n + 1; int ways = x * x * (x * x - 1) / 12; return ways; } // Driver code public static void Main(String []args) { String str = "ab"; int n = str.Length; Console.WriteLine(cntWays(str, n)); } } // This code is contributed by Rajput-Ji
Javascript
<script> // Javascript implementation of the approach // Function to return the number of ways // to insert the bracket pairs function cntWays(str, n) { var x = n + 1; var ways = x * x * (x * x - 1) / 12; return ways; } // Driver code var str = "ab"; var n = str.length; document.write(cntWays(str, n)); // This code is contributed by rutvik_56. </script>
Producción:
6
Complejidad de tiempo: O(1)
Espacio Auxiliar: O(1)