Duplicate Parenthesis

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
26 upvotes
Asked in companies
Morgan StanleyRakuten India

Problem statement

You are given the expression ‘expr’ with parenthesis. Your task is to find if the given expression contains duplicate parenthesis. A set of parenthesis is duplicate if multiple parenthesis surrounds the same subexpression.

For Example: 
You are given ‘expr’ = “(a+b)+((c+d))”, here the subexpression “c+d” is surrounded by two parentheses. Hence the expression contains duplicate parenthesis. Hence the answer is “YES”.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains a single integer ‘T’, representing the number of test cases.

The first line of each test case contains a string, ‘expr’, representing the given expression.
Output Format: 
For each test case, print “YES” if the expression contains a duplicate parenthesis. Otherwise, print “NO”.

Print a single line for each test case.
Constraints: 
1 <= T <= 10
1 <= |expr| <= 10^6

Time Limit: 1 sec
Note: 
You do not need to print anything. It has already been taken care of. Just implement the function.
Sample Input 1:
2
(a+b)+((c+d))
((a+b) + c)
Sample Output 1:
YES
NO
Explanation:
For the first test case,  ‘expr’ = “(a+b)+((c+d))”, here, the subexpression “c+d” is surrounded by two parentheses. Hence the expression contains duplicate parenthesis. Hence the answer is “YES”.

For the second test case, ‘expr’ = “((a+b) + c)”, here, no subexpression is surrounded by multiple parentheses. Hence the answer is “NO”.
Sample Input 2:
2
(a+b)+((c+d))
((a+b)+(c+d))
Sample Output 2:
YES
NO
Hint

Try to use the stack.

Approaches (1)
Stack

In this approach, we will use the stack data structure and iterate through every character in the expression of the character is not a closed parenthesis ( ( ) then, we push it to the top of the stack. Otherwise, if a closing parenthesis is found we pop the stack until a ‘(‘ is found. If the number of characters between the parenthesis is not greater than 1 then return false. Otherwise, return true.

 

Algorithm: 

  • Initialise an empty stack st.
  • Iterate ch through expr
    • If ch is not ), then insert ch into st
    • Otherwise,
      • Set top as the top of the st and pop the st
      • Set counter as 0
      • While top of the stack is not equal to (
        • Pop the stack st
        • Increase counter by 1
      • If the counter is less than 1 return true
  • Return false
Time Complexity

O(N), Where N is the length of the expression.

 

We are iterating over the expression once, which will cost O(N) time. Hence the overall time complexity is O(N).

Space Complexity

O(N), Where N is the length of the expression.

 

We are maintaining a stack that will have N elements in the worst case and will cost O(N) space. Hence the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Duplicate Parenthesis
Full screen
Console