PROBLEM LINK:
Editorialist: Adithya Dsilva
DIFFICULTY:
SIMPLE
PREREQUISITES:
PROBLEM:
You are given a well-bracketed sequence (consisting of ()
or []
brackets). You have to determine:
- The maximum alternating depth of the sequence.
The alternating depth tells us the maximum number of times we switch between the two types of brackets when we have inner matched brackets enclosed within outer matched brackets. The alternating depth of()[[[]]]
is 1, alternating depth of()([])
is 2, alternating depth of([[()]])
is 3. - The maximum number of symbols between any pair of matched brackets (inclusive of the outer brackets) of type
()
. - The maximum number of symbols between any pair of matched brackets (inclusive of the outer brackets) of type
[]
.
EXPLANATION:
Let us first start by finding the maximum number of symbols between any pair of matched brackets of type ()
and []
.
Let x and y\space (y > x) be the indices of an opening bracket and its corresponding closing bracket in the array. The count of symbols between this bracket pair is
which is inclusive of the outer brackets. The above equation can be verified trivially.
Thus, we can iterate through all the bracket pairs of type ()
and []
, and find the maximum count of symbols over all the bracket pairs of a particular type.
But how are we going to find the index y of the closing bracket corresponding to a opening bracket at x? We use stacks
here!
A nice article on stacks
has been linked in the pre-requisites, which newbies ought to read before proceeding!
We are going to have 2 stacks RBrac
and SBrac
, where RBrac
is for ()
type brackets, and SBrac
is for []
type brackets. What do these stacks store exactly?
For every opening bracket that we encounter, we push the current index (aka the index of this opening bracket) into the respective stack
.
On encountering a closing bracket, it’s corresponding opening bracket is the topmost element present in the respective stack
at this point.
Proof by Reason
Notice that the topmost element in the stack
is the most recent opening bracket that we have encountered (or I can say processed).
Since the sequence is well-bracketed, inner brackets have to be matched before the outer brackets are matched.
Thus, applying the properties of a well-bracketed sequence, we know that the topmost element in a stack
corresponds to the closing bracket that we encounter.
Since the stack stores the index of the opening brackets, we have the value of x in this bracket pair. Also, the index of this closing bracket is y. Using this info, we can now determine the symbol count between this bracket pair, and subsequently find the maximum over all bracket pairs (of the same type ofc ).
A simple code for the above explanation would be as follows:
int maxR = 0; //maximum symbol count between () brackets
int maxS = 0; //maximum symbol count between [] brackets
stack<int> RBrac, SBrac; //Stacks for the opening brackets index
for(int x = 1; x <= N; x++){ //1 based indexing
//Let the bracket at index x be `i`
switch(i){ //Check which type of bracket it is
case 1: //It is a ( bracket
RBrac.push(x);
case 2: //It is a ) bracket
maxR = max(maxR, x - RBrac.top() + 1); //Eq as above
RBrac.pop(); //Remove this bracket as it is matched!
case 3: //It is a [ bracket
SBrac.push(x);
case 4: //It is a ] bracket
maxS = max(maxS, x - SBrac.top() + 1); //Eq as above
SBrac.pop();
}
}
//Break has been ommited to keep the code clean!
//The maximum's are therefore maxR and maxS respectively
Now lets come back to finding the maximum alternating depth of the sequence. We proceed by using stack
’s again!
Let us start by redefining the alternating depth of an opening bracket in a sequence.
The alternating depth tells us the maximum number of times we switch between the two types of brackets when we have inner matched brackets enclosed within outer matched brackets.
Let the alternating depth of an opening bracket be the number of times we switched between the two types of opening brackets (which enclose this opening bracket) before reaching this bracket. The alternating depth of an outermost bracket (a bracket without parents) is 1. A detailed explanation is given below.
Example
Let the bracket sequence be ([([](()))])
The alternating depth of the opening brackets in their order of their appearance is \{1,2,3,4,3,3\}.
I’m going to illustrate the alternating depth of the 5^{th} opening bracket in the above sequence. The nesting structure starting from the outermost bracket is as follows:
where the last bracket above corresponds to the 5^{th} opening bracket. Since we switch from (
to [
to (
, the number of switches is 3. Thus the depth of the 5^{th} opening bracket is 3.
Thus, the alternating depth of a sequence is the maximum over the alternating depth of all opening brackets in the sequence!
If the parent of an opening bracket is of the alternate type, then there is a switch of bracket while moving from the parent to the current bracket. Thus the depth of this bracket is 1 more than the depth of the parent bracket.
If the parent of an opening bracket is of the same type, then the depth of this bracket is the same as the depth of the parent bracket.
An explanation (by example) has been given above!
Now, coming to the implementation. We make a stack AltDepth
, where the topmost element corresponds to the depth of the most recent unmatched, opening bracket. The depth of an outermost bracket is 1 (bare case).
Now while iterating through the input, if we encounter an opening bracket, we check if the parent of this bracket is of the alternate type.
-
YES : The depth of this bracket is 1 more than the depth of it’s parent bracket. The depth of the parent bracket is stored at the top of
AltDepth
, since the topmost value inAltDepth
represents the most recent unmatched bracket aka the parent bracket of the current sequence. Thus we addAltDepth.top() + 1
into thestack
, which would then represent the depth of the most recent unmatched bracket. -
NO : The depth of this bracket is the same as the depth of it’s parent bracket. Thus we add
AltDepth.top()
into thestack
, which now represents the depth of the most recent unmatched bracket sequence.
On encountering a closing bracket, we simply remove the topmost element from AltDepth
, as this bracket is no longer unmatched (so this bracket pair is no longer the parent of any other preceding brackets).
Thus, the maximum value that was present in the stack AltDepth
determines the maximum alternating depth of the sequence!
Wait! How do we determine the parent bracket’s type? Simple. We check stacks RBrac
and SBrac
for the most recent opening bracket, which would be the parent bracket of the current bracket we are processing.
CODE SNIPPET:
int maxR = 0; //maximum symbol count between () brackets
int maxS = 0; //maximum symbol count between [] brackets
int maxDepth = 0; //maximum alternating depth of the sequence
stack<int> RBrac, SBrac; //Stacks for the opening brackets index
stack<int> AltDepth; //Stack for the alt depth of the sequence
for(int x = 1; x <= N; x++){ //1 based indexing
//Let the bracket at index x be `i`
switch(i){ //Check which type of bracket it is
case 1: //It is a ( bracket
//Check parent bracket type by checking the type of the most
//recent opening bracket
if(RBrac.top() < SBrac.top())
AltDepth.push(AltDepth.top() + 1);
else
AltDepth.push(AltDepth.top());
RBrac.push(x);
case 2: //It is a ) bracket
maxR = max(maxR, x - RBrac.top() + 1); //Eq as above
RBrac.pop(); //Remove this bracket as it is matched!
AltDepth.pop(); //Remove this depth as it is matched!
case 3: //It is a [ bracket
//Check parent bracket type by checking the type of the most
//recent opening bracket
if(SBrac.top() < RBrac.top())
AltDepth.push(AltDepth.top() + 1);
else
AltDepth.push(AltDepth.top());
SBrac.push(x);
case 4: //It is a ] bracket
maxS = max(maxS, x - SBrac.top() + 1); //Eq as above
SBrac.pop(); //Remove this bracket as it is matched!
AltDepth.pop(); //Remove this depth as it is matched!
}
maxDepth = max(maxDepth, AltDepth.top());//Max depth in sequence
}
cout << maxDepth << maxR << maxS << endl;
//Remember to add spaces between the ouptut!
//Break has been ommited to keep the code clean!
TIME COMPLEXITY:
Since only one iteration is made through the entire array, the time complexity of the above code is
MEMORY COMPLEXITY:
RBrac
and SBrac
combined can have at most \frac{N}{2} values (since there are exactly \frac{N}{2} opening brackets). AltDepth
can also have at most \frac{N}{2} values in it. Thus the overall memory complexity is
SIMILAR PROBLEMS:
SOLUTIONS:
Editorialists solution can be found here.
Did you like the editorial? Do you have any other approaches to the problem? Any suggestions? Comment them below!
Experimental: For better evaluation of my editorials, I request all readers to rate the editorial (on a scale from 1-5, where 5 represents an awesome editorial)
- 1
- 2
- 3
- 4
- 5
0 voters
Also don’t forget to up-vote this post if you liked it !