i am not able to think of the solution with the stuff i learned from the course so far please help me, give me the approach how to solve it
Not able to think of solution
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).