Brackets all over

#1

Not able to understand the question at all, Please explain.

Brackets all over
Brackets all over
#2

hi @Yuvraj_Luhach
In this question, you need to answer the number of different combinations of string a & b that can be used to make a + s + b balanced under the constraint that the length of a + s + b should be n.

The statement “At any index, number of opening brackets should be greater than closing brackets” should be “At any index, number of opening brackets should be greater or equal to number of closing brackets”

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#4

here is my code which passed 2 test case out of 5:

import java.util.*;
public class Main {
public static long Parantheses(int n, String ans) {
int right = 0,left = 0;
for (int i = 0; i < ans.length(); i++) {
if (ans.charAt(i) == ‘(’)
right++;
else
left++;
if (left > right)
return 0;
}
if (ans.length() == n) {
if (right == left) {
// System.out.println(ans);
return 1;
} else
return 0;
}
long M = 1000_000_007;
return Parantheses(n, ans + “)”) % M + Parantheses(n, ans + “(”) % M
+ Parantheses(n, “)” + ans) % M + Parantheses(n, “(” + ans) % M;
}
public static void main(String args[]) {
Scanner in = new Scanner(System.in);
int n = in.nextInt(), m = in.nextInt(), right = 0, left = 0;
String ce = in.nextLine(), str = in.nextLine();
System.out.println(Parantheses(n, str));
}
}

#5

can you tell me where I am wrong , or is there any efficient approach to this question
I have tried doing it through recursion

#6

here is my code which passed 2 test case out of 5:

import java.util.*;
public class Main {
public static long Parantheses(int n, String ans) {
int right = 0,left = 0;
for (int i = 0; i < ans.length(); i++) {
if (ans.charAt(i) == ‘(’)
right++;
else
left++;
if (left > right)
return 0;
}
if (ans.length() == n) {
if (right == left) {
// System.out.println(ans);
return 1;
} else
return 0;
}
long M = 1000_000_007;
return Parantheses(n, ans + “)”) % M + Parantheses(n, ans + “(”) % M
+ Parantheses(n, “)” + ans) % M + Parantheses(n, “(” + ans) % M;
}
public static void main(String args[]) {
Scanner in = new Scanner(System.in);
int n = in.nextInt(), m = in.nextInt(), right = 0, left = 0;
String ce = in.nextLine(), str = in.nextLine();
System.out.println(Parantheses(n, str));
}
}

#7

your approach has two key problems:

  1. its time complexity is exponential , as the recursion tree will have branch factor of 4, and its depth in worst case is 1200, since n-m<=1200… so TC could be 4^1200
  2. you are checking the first condition(opening brackets > closing brackets at all indices) for partial solutions as well, which is not right,
    think about the case where str = “))”… and n=4… you will never get solution for this problem through your approach.
    you need to improvise your approach, think about it.

thanks

#8

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.