Redundant Brackets

Easy
0/40
Average time to solve is 15m
304 upvotes
Asked in companies
AdobeUberUKG (Ultimate Kronos Group)

Problem statement

Given valid mathematical expressions in the form of a string. You are supposed to return true if the given expression contains a pair of redundant brackets, else return false. The given string only contains ‘(‘, ’)’, ‘+’, ‘-’, ‘*’, ‘/’ and lowercase English letters.

Note :

A pair of brackets is said to be redundant when a subexpression is surrounded by needless/ useless brackets.

For Example : 
((a+b)) has a pair of redundant brackets. The pair of brackets on the first and last index is needless. 
While (a + (b*c)) does not have any pair of redundant brackets.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ denoting the number of test cases. The test cases follow.

The first line of each test case contains a string denoting the expression.
Output Format : 
For each test case, return “Yes” if the given expression contains at least one pair of redundant brackets, else return “No”.
Note : 
You don’t need to print anything; It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 50
3 <= |S| <= 10^4

Time Limit: 1 sec
Sample Input 1 :
2
(a+b)
(a+c*b)+(c))
Sample Output 1 :
No
Yes
Explanation of Sample Input 1 :
In the first test case, there are no redundant brackets. Hence, the output is “No”. 


In the second test case, the brackets around the alphabet ‘c’( index 8 and index 10) are redundant. Hence the output is “Yes”.
Sample Input 2 :
2
(a*b+(c/d))
((a/b))
Sample Output 2 :
No
Yes
Explanation of Sample Input 2 :
In the first test case, there are no redundant brackets. Hence, the output is “No”. 


In the second test case, the brackets around the subexpression “(a+b)” ( index 0 and index 6) are redundant. Hence the output is “Yes”.
Hint

Can you think about using a stack to find redundant brackets?

Approaches (1)
Stack Based Approach

The idea is to use the stack to keep track of the opening and closing brackets. If we remove any subexpression from the given string which is enclosed by “()” and after that, if there exist any pair of opening and closing brackets“()” which does not have any operator(‘+’,’-’,’*’,’/’) in between them, then the expression will have a redundant pair of brackets.

 

The steps are as follows :

  1. Define a stack, for keeping track of pairs of opening and closing brackets, let’s say ‘BRACKETS’.
  2. Iterate through the string and whenever we encounter an opening bracket or an operator( { ‘(’, ‘+’, ‘-’, ‘*’, ‘/’, } ) we will push the current character to the stack(‘BRACKETS’).
  3. Whenever we encounter ‘)’ in the string
    1. Now we will pop characters from the stack(‘BRACKETS’) until we pop an opening bracket { ‘(‘ }  from the stack.
    2. If we find any operator ( { ‘+’, ‘-’, ‘*’, ‘/’ } )  before encountering ‘(’ then the current bracket is not redundant.
    3. If we do not find any operator, then the current bracket is redundant. Hence we will return true.
  4. If there is no redundant bracket, then return false.
Time Complexity

O(|S|), where |S| is the length of the given string.

 

We are iterating through the given string which will take O(|S|) time. Also, we are performing push and pop operations on a stack which take constant time. Thus, the total time complexity is O(|S|).

Space Complexity

O(|S|), where |S| is the length of the given string.

 

We are using a stack for keeping track of brackets, in the worst case when there are no brackets and all the characters in the string are either operators or operands the size of the stack will become |S|. Thus, the overall space complexity will be O(|S|).

Code Solution
(100% EXP penalty)
Redundant Brackets
Full screen
Console