Mam again im not getting what question is trying to say can you please provide with some more sample input

#1

mam again im not getting what question is trying to say can you please provide with some more sample input.
for the problem Brackets all over

#2

hey @pssharma1410
the problem says that you are given a string s , it’s length m and a number n . You have generate all possible pairs of a and b such that:
a + s + b is a valid sequence of brackets of length exactly n .
For example if you are given s = “))” and n = 6(m = 2 obviously) then you can generate following pairs of a and b to make a+s+b a valid sequence:

“()((” “))” “” // Remeber a and b can be blank also.
“((” “))” “()”
“(((” “))” “)”
“(()(” “))” “”
“((()” “))” “”

Hence, the ans for this testcase is 5. If there is no possible combination then print -1. Pls try the question now

#3

mam in the sample test case (int the problem) why the ans is 1 because we can make a pair case. Where

#4

okay I got it mam thank you

1 Like
#5

mam for no possible pair we have to print zero or -1 because in question -1 is written and also 0 is written please confirm

#6

mam I just want a answer that the algo which will be used I this question is my range or not and my range is(Course content before strings):sweat_smile:

#7

Approach

  • It is quite obvious that we would only add opening brackets ‘(’ to string A and only closing brackets ‘)’ to string B
  • Since the number of open and close brackets must be equal, we can never generate a valid string if n is odd.
  • Count the total number of opening and closing brackets required to balanced the string. The opening brackets will go in string A and the closing brackets will go in string B.
  • We start from pos = 0 and go till pos = n - m + 1. At each instance we consider three possibilities.
  • if closingBrackets have not been implemented yet (close==0) and count of open brackets that we have implemented is more than required (open >= openBrackets) then, we implement the closing brackets required for string B and raise a flag for the same by marking close=1 also, change the open bracket count accordingly for this case
  • if we have some open brackets then, put a closing bracket to balance it and decrease open count to denote there is one less unbalanced open bracket now
    add another opening bracket to the string so far. This bracket will be initially unbalanced.
  • We add the results obtained from the three possibilities. We store and return this result.
  • Continue the above process till pos < n-m+1.
  • At pos == n-m+1, we must ensure that all required opening and closing brackets have been implemented. We do so by checking the status of out flag variable close i.e. check close==1.

Also make sure there are no pending unbalanced open brackets (open==0).
You can refer to this code

#8

it will be 0 if no possible pair. that must be a typo