Given a string str of length N, the task is to find the number of ways to insert only 2 pairs of parentheses into the given string such that the resultant string is still valid.
Examples:
Input: str = “ab”
Output: 6
((a))b, ((a)b), ((ab)), (a)(b), (a(b)), a((b))
which are a total of 6 ways.
Input: str = “aab”
Output: 20
Approach: it can be observed that for the lengths of the string 1, 2, 3, …, N a series will be formed as 1, 6, 20, 50, 105, 196, 336, 540, … whose Nth term is (N + 1)2 * ((N + 1)2 – 1) / 12.
Below is the implementation of the above approach:
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> |
6
Time Complexity: O(1)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!