Bracket Number

Easy
0/40
Average time to solve is 15m
profile
Contributed by
4 upvotes
Asked in companies
GoogleFlipkartDunzo

Problem statement

Given a string ‘S’ comprising of some brackets. You need to print the number of every bracket.

For Example: 
If S = (pq)() 
Then the output will be 1 1 2 2. First pair of opening and closing brackets will get the same number and so does the 2nd pair.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains a single integer ‘T’ denoting the number of test cases.

The first line of each test case contains a string ‘S’.
Output Format: 
For each test case, print the number of every bracket separated by a space.

Output of each test case will be printed on a new line.
Note: 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 50
1 <= |S| <= 10^5

Where ‘|S|’ is the length of a particular string.

Time Limit: 1 Sec
Sample Input 1:
2
ab(cd)(e)
(zyz)
Sample Output 1:
1 1 2 2
1 1
Explanation For Sample Input 1:
Test Case 1: In the given string, there are two pairs of brackets and the order is 1 1 2 2.

Test Case 2: There is only one pair of brackets. So the number of brackets is 1 1.
Sample Input 2:
2
(())()
a(b(pq)(t))
Sample Output 2
1 2 2 1 3 3
1 2 2 3 3 1
Explanation For Sample Input 2:
Test Case 1: In the given string, there are three pairs of brackets and the order is 1 2 2 1 3 3.

Test Case 2: In the given string, there are three pairs of brackets and the order is 1 2 2 3 3 1.
Hint

Try to iterate through entire string and take note of all starting and ending parenthesis.

Approaches (1)
Stack Implementation

Approach: The basic idea to solve this problem is to use a stack. We will maintain a stack ‘STACK’ and a variable ‘CNT’ which will keep the count number of brackets. When ‘(‘ is encountered we will increment the ‘CNT’ and push it in the ‘STACK’ and ‘RES’ vector. When ‘)’ is encountered we will pop the top element of the ‘STACK’ and push it in ‘RES’ vector.

 

Algorithm:

 

  1. Take a stack ‘STACK’ and a vector ‘RES’ to store the result.
  2. Initialize a variable ‘CNT’ to ‘0’.
  3. Traverse the string from ‘i’ equals 0 to ‘S.length’.
    • If S[i] equals ‘(‘.
      • Increment ‘CNT’
      • Push ‘CNT’ in STACK.
      • Push ‘CNT’ to ‘RES’
    • If S[i] equals ‘)’
      • Initialize ‘TEMP’ as ‘STACK.top( )’.
      • Pop top from ‘STACK’.
      • Push ‘TEMP’ to ‘RES’
  4. Return ‘RES’.
Time Complexity

O(N), where ‘N’ is the length of the string ‘S’.

 

We have traversed the string ‘S’ one time. So complexity will be in the order of length of the string.

Space Complexity

O(N), where ‘N’ is the length of the string ‘S’.

 

We have used extra space for the stack which makes the space complexity O(N).

Code Solution
(100% EXP penalty)
Bracket Number
Full screen
Console